On 03/04/2015 03:23 PM, Ali Çehreli wrote:> On 03/04/2015 02:18 PM, Josh
wrote:
>
> > now say A[] was = [90, 50, 33, 72, 35]
> >
> > and by the end of the function B[] = [33, 50, 72, 90, 35]
> >
> >
> > now we call swap(A,B) and A would now = [33, 35, 50, 72, 90]
> >
> > and somehow the 35 moves in front of the 50.
>
> Not for me. I think there is bug in the algorithm:
>
> auto a = [90, 50, 33, 72, 35];
> a.mergeSort;
> assert(a == [33, 50, 72, 90, 35]); // Incorrect ordering :(
The bug is, what is sorted remains in mergeSort() as its parameter A.
Due to a number of swaps, A may be what used to be B, which is quite a
different slice from the callers. :(
Here is a very quick fix that requires a different usage:
// (1) return the sorted slice
T[] mergeSort(T)(T[] A) pure nothrow @safe
out (result) {
assert(result.isSorted); // (2) what is returned is checked
} body {
// ...
return A; // (3) return the sorted range
}
a = a.mergeSort; // (4) the caller must assign back
// to the original slice
Now it is sorted:
[33, 35, 50, 72, 90]
Ali
