最快的安全排序算法实现

Question

我花了一些时间在C#中实现快速排序算法.完成后我比较了我的实现速度和C#的Array.Sort-Method.

我只是比较了随机int数组的速度.

这是我的实现:

static void QuickSort(int[] data, int left, int right)
{
    int i = left - 1,
        j = right;

    while (true)
    {
        int d = data[left];
        do i++; while (data[i] < d);
        do j--; while (data[j] > d);

        if (i < j) 
        {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
        else
        {
            if (left < j)    QuickSort(data, left, j);
            if (++j < right) QuickSort(data, j, right);
            return;
        }
    }
}

性能(当排序长度为100000000的随机int []时):
   - 我的算法:14.21秒
   - .Net Array <int> .Sort:14.84秒

有谁知道如何更快地实现我的算法？
或者任何人都可以提供更快的实施(不一定是快速排序!),我跑得更快？

注意:
   - 请不要使用多核/处理器来提高性能的算法
   - 只有有效的C#源代码

如果我在线的话,我会在几分钟内测试所提算法的性能.

编辑:
您认为对于包含少于8个值的零件使用理想的分拣网络会提高性能吗？

Answer 1

二进制插入排序几乎总是赢得短期运行(~10项).由于简化的分支结构,它通常比理想的分拣网络更好.

双枢轴快速排序比快速排序快.链接的文章包含一个您可能适应的Java实现.

如果您只对整数进行排序,那么在长数组上基数排序可能会更快.

Answer 2

有谁知道如何更快地实现我的算法？

通过将代码转换为使用指针,我能够节省10%的执行时间.

    public unsafe static void UnsafeQuickSort(int[] data)
    {
        fixed (int* pdata = data)
        {
            UnsafeQuickSortRecursive(pdata, 0, data.Length - 1);
        }
    }

    private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right)
    {
        int i = left - 1;
        int j = right;

        while (true)
        {
            int d = data[left];
            do i++; while (data[i] < d);
            do j--; while (data[j] > d);

            if (i < j)
            {
                int tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
            else
            {
                if (left < j) UnsafeQuickSortRecursive(data, left, j);
                if (++j < right) UnsafeQuickSortRecursive(data, j, right);
                return;
            }
        }
    }