Quick implementation of the sorting algorithm

Question

I spent some time implementing the quicksort algorithm in C #. After graduation, I compared the speed of my implementation with C # Array.Sort-Method.

I just compare speed with random int arrays.

Here is my implementation:

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

Performance (when sorting a random int [] with a length of 100000000):
- my algorithm: 14.21 seconds
-.Net Array <int> .Sort: 14.84 seconds

Does anyone know how to implement my algorithm even faster?
Or can someone provide a faster implementation (not necessarily a quick sort!), Which is my run faster?

:
- , , / - #

, .

EDIT:
, , 8 , ?

Answer 1

- , ?

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 2

(~ 10 ). , - .

, quicksort. Java, , , .

, radix, , .

Answer 3

: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html http://home.westman.wave.ca/~rhenry/sort/.

# Shear : http://www.codeproject.com/KB/recipes/cssorters.aspx.

Java examples, but it's terribly close to C #. They are parallel because they run faster on multiple cores, but still have to be very fast.

Answer 4

This first (and probably second) quicksort algorithm breaks when sorting arrays with duplicate elements. I used this one which works great.