Самая быстрая реализация алгоритма сортировки

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;
        }
    }
}

Производительность (при сортировке случайного типа int [] длиной 100000000):
- мой алгоритм: 14,21 секунды
- .Net Array .Sort: 14,84 секунды

Кто-нибудь знаеткак реализовать мой алгоритм еще быстрее?
Или кто-нибудь может предложить более быструю реализацию (не нужно быть быстрой сортировкой!), которая будет работать быстрее?

Примечание:
- пожалуйста, не используйте алгоритмы, которые используют несколько ядер/ процессоры для улучшения производительности
- только действительный исходный код C #

Я проверю работоспособность предоставленных алгоритмов в течение нескольких минут, если я в сети.

РЕДАКТИРОВАТЬ:
Как вы думаете, использование идеальной сети сортировки для деталей, содержащих менее 8 значений, улучшит производительность?

Answer 1

Бинарная сортировка вставок почти всегда выигрывает при коротких сериях (~ 10 позиций).Часто это лучше, чем идеальная сортировочная сеть из-за упрощенной структуры ветвления.

Быстрая сортировка с двумя поворотами быстрее, чем быстрая сортировка.Связанный документ содержит реализацию Java, которую вы, вероятно, могли бы адаптировать.

Если вы сортируете только целые числа, radix sort , вероятно, будет еще быстрее работать с длинными массивами.

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;
            }
        }
    }

Answer 3

Этот первый (и, вероятно, второй) алгоритм быстрой сортировки прерывается при сортировке массивов с дублирующимися элементами.Я использовал этот один, который отлично работает.

Answer 4

Посмотрите на сортировку по сдвигу и сортировку нечетных событий: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html и http://home.westman.wave.ca/~rhenry/sort/.

Здесь есть реализация сортировки по сдвигу на C #: http://www.codeproject.com/KB/recipes/cssorters.aspx.

Примеры на Java, но это очень близко к C #.Они параллельные, потому что они работают быстрее на нескольких ядрах, но все равно должны быть очень быстрыми.