## digitalmars.D.bugs - [Issue 8331] New: Problem with sort!(SwapStrategy.stable)

d-bugmail puremagic.com writes:
```http://d.puremagic.com/issues/show_bug.cgi?id=8331

Summary: Problem with sort!(SwapStrategy.stable)
Product: D
Version: D2
Platform: All
OS/Version: All
Status: NEW
Severity: normal
Priority: P2
Component: Phobos
AssignedTo: nobody puremagic.com
ReportedBy: bearophile_hugs eml.cc

--- Comment #0 from bearophile_hugs eml.cc 2012-07-01 08:59:04 PDT ---
In this program I have used sort!(SwapStrategy.stable) on a small amount of
data, and I have compared its results with two very different stable sorts (an
insertion sort and a merge sort). The insertion sort and the merge sort give
the same results, but their result is different from
sort!(SwapStrategy.stable):

import std.stdio, std.algorithm, std.array, std.range;

enum a =
[45,8,94,23,30,61,99,48,49,92,32,1,71,45,6,65,54,34,37,7,64,80,9,23,33,30];

enum b =
[45,55,38,66,89,82,92,70,92,86,63,25,95,45,3,84,42,58,70,83,98,53,72,36,88,0];

static assert(a.length == b.length);

bool myLess(in int i, in int j) pure nothrow {
return b[i] * a[j] > b[j] * a[i];
}

void insertionSort(T)(T[] data) pure nothrow {
foreach (i, value; data[1 .. \$]) {
auto j = i + 1;
for ( ; j > 0 && myLess(value, data[j - 1]); j--)
data[j] = data[j - 1];
data[j] = value;
}
}

void merge_sort(int[] list2) pure nothrow {
// merge (used by merge_sort_r)
static void merge(int[] list2, in int first, in int last, in int sred) pure
nothrow {
int[] helper_list;
int i = first;
int j = sred + 1;
while (i <= sred && j <= last) {
if (myLess(list2[i], list2[j])) {
helper_list ~= list2[i];
i++;
} else {
helper_list ~= list2[j];
j++;
}
}
while (i <= sred) {
helper_list ~= list2[i];
i++;
}
while (j <= last) {
helper_list ~= list2[j];
j++;
}
foreach (k; 0 .. last - first + 1)
list2[first + k] = helper_list[k];
}

// merge sort recursive (used by merge_sort)
static void merge_sort_r(int[] list2, in int first, in int last) pure
nothrow {
if (first < last) {
const sred = (first + last) / 2;
merge_sort_r(list2, first, sred);
merge_sort_r(list2, sred + 1, last);
merge(list2, first, last, sred);
}
}

merge_sort_r(list2, 0, list2.length -1);
}

void main() {
const c = a.length.iota().array();

auto c1 = c.dup;
sort!(myLess, SwapStrategy.stable)(c1);
writeln(c1);

auto c2 = c.dup;
insertionSort(c2);
writeln(c2);

auto c3 = c.dup;
insertionSort(c3);
writeln(c3);

assert(c2 == c3); // OK
assert(c1 == c2); // asserts
}

-----------------------------------------

With a little more input data sort!(SwapStrategy.stable) gives a "Failed to
sort range":

import std.stdio, std.algorithm, std.array, std.range;

enum a = [22, 45, 8, 94, 23, 30, 61, 99, 48, 49, 92, 32, 1, 71, 45, 6, 65,
54, 34, 37, 7, 64, 80, 9, 23, 33, 30, 19, 30, 97, 40, 42, 7, 7, 52, 5, 35,
50, 92, 14, 17, 8, 72, 23, 33];

enum b = [58, 45, 55, 38, 66, 89, 82, 92, 70, 92, 86, 63, 25, 95, 45, 3,
84, 42, 58, 70, 83, 98, 53, 72, 36, 88, 0, 1, 41, 23, 37, 51, 83, 17, 61,
37, 3, 4, 98, 15, 52, 69, 12, 47, 87];

static assert(a.length == b.length);

bool myLess(in int i, in int j) pure nothrow {
return b[i] * a[j] > b[j] * a[i];
}

void main() {
auto c1 = a.length.iota().array();
c1.sort!(myLess, SwapStrategy.stable)();
writeln(c1);
}

DMD 2.060alpha:

core.exception.AssertError C:\dmd2\src\phobos\std\algorithm.d(6993): Failed to
sort range of type uint[]. Actual result is: [12, 20, 32, 41, 23, 35, 2, 40]...
----------------
0x00417520 in char[][] core.sys.windows.stacktrace.StackTrace.trace()
0x004173AB in core.sys.windows.stacktrace.StackTrace
core.sys.windows.stacktrace.StackTrace.__ctor()
0x0040AD38 in extern (C) int rt.dmain2.main(int, char**).void runMain()
0x0040AD72 in extern (C) int rt.dmain2.main(int, char**).void runAll()
0x0040A994 in main
0x0041F081 in mainCRTStartup
0x77631603 in RtlInitializeExceptionChain
0x776315D6 in RtlInitializeExceptionChain

--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
```
Jul 01 2012
d-bugmail puremagic.com writes:
```http://d.puremagic.com/issues/show_bug.cgi?id=8331

--- Comment #1 from bearophile_hugs eml.cc 2012-07-01 09:03:27 PDT ---
This little Python program gives the same output as the merge sort and
insertion sort (Python built-in sort is stable):

from itertools import imap
a = [45,8,94,23,30,61,99,48,49,92,32,1,71,45,6,65,54,34,37,7,64,80,9,23,33,30]
b =
[45,55,38,66,89,82,92,70,92,86,63,25,95,45,3,84,42,58,70,83,98,53,72,36,88,0]

def cmp(i, j):
if b[i] * a[j] > b[j] * a[i]: return -1
elif b[i] * a[j] < b[j] * a[i]: return 1
return 0

print sorted(range(len(a)), cmp=cmp)

Outputs:
[11, 19, 22, 1, 4, 3, 24, 10, 18, 8, 17, 23, 20, 7, 5, 12, 15, 0, 13, 9, 6, 16,
21, 14, 2, 25]

--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
```
Jul 01 2012
d-bugmail puremagic.com writes:
```http://d.puremagic.com/issues/show_bug.cgi?id=8331

Xinok <xinok live.com> changed:

----------------------------------------------------------------------------
CC|                            |xinok live.com

--- Comment #2 from Xinok <xinok live.com> 2013-02-24 08:57:54 PST ---
Previously, the stable sort in Phobos was broken which may be why this code
failed. It has since been fixed, so if that was indeed the problem, we can
probably close this bug report.

--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
```
Feb 24 2013
d-bugmail puremagic.com writes:
```http://d.puremagic.com/issues/show_bug.cgi?id=8331

bearophile_hugs eml.cc changed:

----------------------------------------------------------------------------
Status|NEW                         |RESOLVED
Resolution|                            |FIXED

--- Comment #3 from bearophile_hugs eml.cc 2013-02-24 13:52:56 PST ---
Previously, the stable sort in Phobos was broken which may be why this code
failed. It has since been fixed, so if that was indeed the problem, we can
probably close this bug report.

Right, thank you. Closed.

--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
```
Feb 24 2013
d-bugmail puremagic.com writes:
```http://d.puremagic.com/issues/show_bug.cgi?id=8331

bearophile_hugs eml.cc changed:

----------------------------------------------------------------------------
Resolution|FIXED                       |WORKSFORME

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