http://d.puremagic.com/issues/show_bug.cgi?id=4584

           Summary: std.algorithm.sort fails with SwapStrategy.stable
           Product: D
           Version: D2
          Platform: Other
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: johannespfau@gmail.com


--- Comment #0 from Johannes Pfau <johannespfau@gmail.com> 2010-08-05 03:17:37 PDT ---
Created an attachment (id=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: "core.exception.AssertError@std.algorithm(4021): Assertion failure"
(the assert is "assert(isSorted!(lessFun)(r));")

Tested with dmd 2.047 and phobos 2.047.
A test case is attached.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei@metalanguage.com
         AssignedTo|nobody@puremagic.com        |andrei@metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584


Olivier Fabre <axel.foster-5bcwppg@yopmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |axel.foster-5bcwppg@yopmail
                   |                            |.com


--- Comment #1 from Olivier Fabre <axel.foster-5bcwppg@yopmail.com> 2011-10-23 17:34:22 PDT ---
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.)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584



--- Comment #2 from Olivier Fabre <axel.foster-5bcwppg@yopmail.com> 2011-10-23 18:52:08 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584


Dmitry Olshansky <dmitry.olsh@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dmitry.olsh@gmail.com


--- Comment #3 from Dmitry Olshansky <dmitry.olsh@gmail.com> 2012-08-22 06:31:15 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #4 from bearophile_hugs@eml.cc 2012-08-22 14:41:50 PDT ---
(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?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584



--- Comment #5 from Dmitry Olshansky <dmitry.olsh@gmail.com> 2012-08-22 22:36:30 PDT ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584


Xinok <xinok@live.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinok@live.com


--- Comment #6 from Xinok <xinok@live.com> 2012-09-03 10:58:38 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584



--- Comment #7 from Dmitry Olshansky <dmitry.olsh@gmail.com> 2012-09-03 14:14:23 PDT ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4584


yebblies <yebblies@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pull
                 CC|                            |yebblies@gmail.com
           Platform|Other                       |All
         AssignedTo|andrei@metalanguage.com     |dmitry.olsh@gmail.com


--- Comment #8 from yebblies <yebblies@gmail.com> 2012-10-28 03:21:52 EST ---
Dmitry's pull:

https://github.com/D-Programming-Language/phobos/pull/787

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------