c# - 最快的安全排序算法实现

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.Sort: 14.84 秒

有谁知道如何更快地实现我的算法？
或者任何人都可以提供更快的实现(不必是快速排序!)，我的运行速度更快吗？

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

如果我在线，我将在几分钟内测试提供的算法的性能。

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

Answer 1

二进制插入排序几乎总能在短期运行(~10 项)中胜出。由于简化了分支结构，它通常比理想的排序网络更好。

Dual pivot quicksort比快速排序更快。

如果你只对整数排序，一个radix sort在长阵列上可能会更快。