Hi everybody!
I spend some time implementing a quicksort algorithm in C#. After finishing I compared the speed of my implementation and C#'s Array.Sort-Method.
I just compare speed working on random int arrays.
Here's 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 an random int[] with 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 anyone provide a faster implementation (need not be a quicksort!) which my run faster?
Note:
- please no algorithms which use multiple cores/processors to improve perrformance
- only valid C# source code
I will test the performance of the provided algorithms within a few minutes if I'm online.
EDIT:
Do you think using a ideal sorting network for parts containing less than 8 value would improve performance?