Sorts.cs

/*
Results for a 1<<24 size ulong array filled with random data:

              Method |     Mean |    Error |   StdDev |
-------------------- |---------:|---------:|---------:|
   BottomUpMergeSort | 544.7 ms | 2.119 ms | 1.982 ms |
           QuickSort | 242.8 ms | 4.754 ms | 4.669 ms |
    TopDownMergeSort | 435.3 ms | 1.393 ms | 1.303 ms |
 AltTopDownMergeSort | 452.9 ms | 1.488 ms | 1.392 ms |
     SystemArraySort | 263.1 ms | 2.225 ms | 2.081 ms |

*/

static void BottomUpMergeSort(T[] target, T[] scratchSpace, int n)
{
    const int insertionSortBatchSize = 48;

    var batchesSortedUpto = 0;
    while (true) {
        if (batchesSortedUpto + insertionSortBatchSize <= n) {
            InsertionSort_InPlace(target, batchesSortedUpto, batchesSortedUpto + insertionSortBatchSize);
            batchesSortedUpto += insertionSortBatchSize;
        } else {
            if (n - batchesSortedUpto >= 2) {
                InsertionSort_InPlace(target, batchesSortedUpto, n);
            }
            break;
        }
    }

    var A = target;
    var B = scratchSpace;

    for (var width = insertionSortBatchSize; width < n; width = width << 1) {
        var i = 0;
        while (i + width + width <= n) {
            Merge(A, i, i + width, i + width + width, B);
            i = i + width + width;
        }
        if (i + width < n) {
            Merge(A, i, i + width, n, B);
        } else {
            CopyArray(A, i, n, B);
        }
        var tmp = A;
        A = B;
        B = tmp;
    }
    if (target != A) {
        CopyArray(A, 0, n, target);
    }
}

static void AltTopDownMergeSort(T[] items, T[] scratch, int n)
{
    CopyArray(items, 0, n, scratch);
    TopDownSplitMerge_Either(items, 0, n, scratch);
}

static void TopDownSplitMerge_Either(T[] items, int iBegin, int iEnd, T[] scratch)
{
    if (iEnd - iBegin < 48) {
        InsertionSort_InPlace(items, iBegin, iEnd);
        return;
    }
    int iMiddle = (iEnd + iBegin) / 2;
    TopDownSplitMerge_Either(scratch, iBegin, iMiddle, items);
    TopDownSplitMerge_Either(scratch, iMiddle, iEnd, items);
    Merge(scratch, iBegin, iMiddle, iEnd, items);
}

static void TopDownMergeSort(T[] items, T[] scratch, int n)
{
    var iters = Utils.LogBase2RoundedDown((uint)(n >> InsertionSortPower));

    if ((iters & 1) == 0) {
        TopDownSplitMerge_Even(items, 0, n, scratch, iters);
    } else {
        TopDownSplitMerge_Odd(items, 0, n, scratch, iters);
    }
}

static void TopDownSplitMerge_Even(T[] items, int iBegin, int iEnd, T[] scratch, int itersToGo)
{
    if (itersToGo == 0) {
        InsertionSort_InPlace(items, iBegin, iEnd);
        return;
    }
    int iMiddle = (iEnd + iBegin) / 2;
    TopDownSplitMerge_Even(scratch, iBegin, iMiddle, items, itersToGo - 1);
    TopDownSplitMerge_Even(scratch, iMiddle, iEnd, items, itersToGo - 1);
    Merge(scratch, iBegin, iMiddle, iEnd, items);
}

static void TopDownSplitMerge_Odd(T[] items, int iBegin, int iEnd, T[] scratch, int itersToGo)
{
    if (itersToGo == 0) {
        InsertionSort_Copy(scratch, iBegin, iEnd, items);
        return;
    }
    int iMiddle = (iEnd + iBegin) / 2;

    TopDownSplitMerge_Odd(scratch, iBegin, iMiddle, items, itersToGo - 1);
    TopDownSplitMerge_Odd(scratch, iMiddle, iEnd, items, itersToGo - 1);
    Merge(scratch, iBegin, iMiddle, iEnd, items);
}

public static void CopyArray(T[] source, int iBegin, int iEnd, T[] target)
{
    for (int k = iBegin; k < iEnd; k++) {
        target[k] = source[k];
    }
}

static void Merge(T[] source, int iBegin, int iMiddle, int iEnd, T[] target)
{
    int i = iBegin, j = iMiddle, k = iBegin;
    //Assume merge is non-empty; otherwise, you'd need something like...
    //if(i==iMiddle) {
    //    while(j<iEnd)
    //        target[k++] = source[j++];
    //    return;
    //}
    //if(j==iEnd) {
    //    while(i<iMiddle)
    //        target[k++] = source[i++];
    //    return;
    //}

    while (true) {
        if (!Ordering.LessThan(source[j], source[i])) {
            target[k++] = source[i++];
            if (i == iMiddle) {
                while (j < iEnd) {
                    target[k++] = source[j++];
                }
                return;
            }
        } else {
            target[k++] = source[j++];
            if (j == iEnd) {
                while (i < iMiddle) {
                    target[k++] = source[i++];
                }
                return;
            }
        }
    }
}