Parallel Merge Sort

Ali Çehreli via Digitalmars-d digitalmars-d at puremagic.com
Wed Mar 4 15:43:52 PST 2015


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



More information about the Digitalmars-d mailing list