Created attachment 704
test case
When using SwapStrategy.stable with std.algorithms sort function, I get
partially wrong results. It works fine with SwapStrategy.unstable. It also
asserts: "[email protected](4021): Assertion failure"
(the assert is "assert(isSorted!(lessFun)(r));")
Tested with dmd 2.047 and phobos 2.047.
A test case is attached.
Comment #1 by axel.foster-5bcwppg — 2011-10-23T17:34:22Z
I don't know if it helps, but I've got a similar failure with this program:
import std.algorithm;
void main() {
sort!("a<b", SwapStrategy.stable)(
[83, 42, 85, 86, 87, 22, 89, 30, 91, 46, 93, 94, 95, 6,
97, 14, 33, 10, 101, 102, 103, 26, 105, 106, 107, 6]
);
}
It returns:
core.exception.AssertError@/usr/include/d/std/algorithm.d(6662): Failed to sort range of type int[]. Actual result is: [6, 42, 85, 86, 87, 22, 89, 30]...
(With the git version of dmd2 and libphobos2 from 21 oct. 2011.)
Comment #2 by axel.foster-5bcwppg — 2011-10-23T18:52:08Z
Oh well, Johannes' test case actually works fine here, so my bug might be a different one. Unless the value of optimisticInsertionSortGetsBetter in sortImpl() was < 13 at the time...
By experimenting with arrays of growing length filled with random numbers, it becomes clear that my bug happens for arrays of length 26 and never for a smaller length, which hints at a bug in the "pivot" (quick?) sort.
Comment #3 by dmitry.olsh — 2012-08-22T06:31:15Z
Hit this issue in my project. As part of normalization process codepoints are _stably_ sorted by their canonical combining class.
Can dig up a bunch of cases if required but the end result is it rarely works.
Comment #4 by bearophile_hugs — 2012-08-22T14:41:50Z
(In reply to comment #3)
> Hit this issue in my project. As part of normalization process codepoints are
> _stably_ sorted by their canonical combining class.
> Can dig up a bunch of cases if required but the end result is it rarely works.
I have seen this:
https://github.com/blackwhale/phobos/commit/23a1cd0b7fac5b4480fee060e240ddda29bed54e
So is this problem caused by a DMD bug? If this is true are you able to create a minimal example of the bug?
Comment #5 by dmitry.olsh — 2012-08-22T22:36:30Z
(In reply to comment #4)
> (In reply to comment #3)
> > Hit this issue in my project. As part of normalization process codepoints are
> > _stably_ sorted by their canonical combining class.
> > Can dig up a bunch of cases if required but the end result is it rarely works.
>
> I have seen this:
>
> https://github.com/blackwhale/phobos/commit/23a1cd0b7fac5b4480fee060e240ddda29bed54e
>
> So is this problem caused by a DMD bug? If this is true are you able to create
> a minimal example of the bug?
No, it's just that $ works only with arrays (still). And in order for sort(zip(...)) to work I need this minor fix. The bug with stable sort was there for 2 years now and I don't realy know the cause.
Comment #6 by xinok — 2012-09-03T10:58:38Z
I've written a collection of sorting algorithms for D:
https://github.com/Xinok/XSort
I recommend using timsort.d or stablesort.d. mergesort.d is a generic implementation. stablequicksort.d is not recommended.
I've extensively tested each of these modules and can confirm they're stable. More so, they're many times faster than the stable sort in Phobos. Lastly, there are no issues regarding the dollar token $ (range.length is used as necessary).
I provide all of these modules to the public domain. That means anybody is free to implement any of these modules into Phobos.
Comment #7 by dmitry.olsh — 2012-09-03T14:14:23Z
(In reply to comment #6)
> I've written a collection of sorting algorithms for D:
> https://github.com/Xinok/XSort
>
> I recommend using timsort.d or stablesort.d. mergesort.d is a generic
> implementation. stablequicksort.d is not recommended.
>
> I've extensively tested each of these modules and can confirm they're stable.
> More so, they're many times faster than the stable sort in Phobos. Lastly,
> there are no issues regarding the dollar token $ (range.length is used as
> necessary).
Yeah, I recall you had some great stuff on this. Thanks for showing up.
> I provide all of these modules to the public domain. That means anybody is free
> to implement any of these modules into Phobos.
Great, I'll look into making a pull request to do just that.
With a proper attribution, of course.