Bug 8331 – Problem with sort!(SwapStrategy.stable)

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() 0x004026B3 in _Dmain at C:\leonardo\googleCodeJam2012Round3\test3.d(29) 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 0x777BD309 in BaseThreadInitThunk 0x77631603 in RtlInitializeExceptionChain 0x776315D6 in RtlInitializeExceptionChain

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]

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.

(In reply to comment #2) > 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.