C# sort implementation that's as fast or faster than Array.Sort?

[ICESTORM]

Array.Sort is supposedly QuickSort (I think that's what it says on MSDN).

But using a QuickSort algorithm written in C# and comparing it to the built-in sort function Array.Sort, the QuickSort implementation was maybe about 2.5 or more times slower?

Is there a sorting algorithm that will work as fast as the built in algorithm?

And, what I want to do is sort an array of indices
E.g. I have an array of elements, 100 elements, so MyArray[100] (0-99) of elements to be sorted.
And an array of indices MyIndices[100] of indices from 0-99.

So
MyArray [0....1...2..] = Item1, Item2, Item3....
MyIndices[0..1..2..3..]= 0...1...2..3...

Instead of sorting (swapping) the elements in MyArray
I want to only swap the Indices, and the algorithm compares the elements in MyArray.

Is there a way to use Array.Sort or something to do this without making a copy of an array? I think Array.Sort can do it but it just swaps both instead of swapping only the indices, so to keep MyArray intact, you feed it a copy of it.. Array.CopyTo() or something..

I have written a Index Quicksort, but it is about 2-2.5x slower than Array.Sort.
So I want to either be able to do it with the faster built in sort or have a C# implementation that's as fast or faster.

[jmcilhinney]

Is there a sorting algorithm that will work as fast as the built in algorithm?

QuickSort is QuickSort. If you're using QuickSort then you are using the same algorithm. It is your implementation of the algorithm that is the issue, not the algorithm itself. As we haven't seen your implementation, there's no way that we can know where the issue(s) might lie.

I would suggest that you download and install .NET Reflector. It has been a free tool for some time but that is about to end, so everyone should get it while they can. You can then use it to look inside the Framework and see how Array.Sort is implemented.

[ICESTORM]

I tried implementing it like how QuickSort shows up in Reflector, and it was slower (array of 1 million int, random numbers).
Does using Try{} Catch{} and Bounds/Error checking really make it faster?
Was slower with median-of-3 also.

Time went from 297ms to 344+.
Array.Sort does it in 127.

Here's QuickSort, only way I know how to make it faster is by using InsertionSort on small (<= ~12) arrays, that only takes off maybe 20ms.

        public static void QS(int[] a, int min, int max)
        {
            int lo = min, hi = max, pvt = a[(min + max) / 2], swp;

            while (lo <= hi) {
                while (a[lo] < pvt) lo++;
                while (a[hi] > pvt) hi--;
                if (lo > hi) break;

                swp = a[lo]; a[lo] = a[hi]; a[hi] = swp;
                lo++; hi--;
            }
            if (min < hi) QS(a, min, hi);
            if (lo < max) QS(a, lo, max);
        }

[ICESTORM]

Err...
The difference now is only 15ms from C# implementation to Array.Sort.

I was testing it in the IDE/Debug Mode instead of compiling it, so that's why.
So...only a little less to match it.

[Lord_Rat]

Of course, Array.Sort works on anything that implement IComparable - in our case, we have the advantage of knowing the data type. By ensuring we are sorting, say, int's we can implement perhaps the best int-sorting algorithm we can find. But that same algorithm is most likely not optimized for just any object type.

I imagine that's exactly the reason Array.Sort is a Quick Sort - at least it works on everything (everything IComparable anyway).

But let's assume that numbers are the only data type - specifically ints. Radix sort usually is pretty fast. Faster than QuickSort.

You can also Radix Sort other data types as long as you can program a reasonable implementation.

If I find time today, I'll put together a radix sort test for ints.

[Lord_Rat]

I wrote the program and ...

Actually the radix sort is pretty bad on large sets, compared with the built-in Array.Sort:

Creating a new array of 2500000 items
Time: 625,000 ticks
Starting Array.Sort
Time: 6,718,750 ticks
Starting Radix Sort
Time: 213,750,000 ticks
Done

Even on smaller sets, it breaks down:

Creating a new array of 1000 items
Time: 0 ms
Starting Array.Sort
Time: 0 ms
Starting Radix Sort
Time: 16 ms
Done

(All measurements in a runtime version of the exe - not in debug)

[Lord_Rat]

OK, I created my own sort - it basically does a bitwise sort and it's probably very similar to some other sorts out there. But it was what made sense in my head, so I put it to code.

Results (3 times, so I could have a good comparison:

Creating a new array of 10000000 items
Time:              703 ms
Starting Array.Sort
Time:            1,875 ms
Starting Radix Sort
Time:           24,203 ms
Starting MSD Bit Sort
Time:            1,828 ms
Done


Creating a new array of 10000000 items
Time:              609 ms
Starting Array.Sort
Time:            1,641 ms
Starting Radix Sort
Time:           21,297 ms
Starting MSD Bit Sort
Time:            1,500 ms
Done


Creating a new array of 20000000 items
Time:            1,359 ms
Starting Array.Sort
Time:            3,719 ms
Starting Radix Sort
Time:           51,875 ms
Starting MSD Bit Sort
Time:            3,107 ms
Done

The code for my MSD Bit Sort is this:

using System;
using System.Collections.Generic;
using System.Text;

namespace Sort_Comparison
{
	class MSDBit
	{
		public static int[] Sort(int[] Values)
		{
			int MSD = 0;
			for(int i = 0 ; i < Values.Length ; i++)
			{
				//bitwise OR so that we can find the largest possible number
				MSD |= Values[i];
			}

			int iPattern = 0x8000;
			while(iPattern != 0)
			{
				if((MSD & iPattern) == iPattern)
				{
					//Start here
					return MSDSort(Values, iPattern, 0, Values.Length);
				}

				iPattern = iPattern >> 1;
			}

			return Values;
		}

		private static int[] MSDSort(int[] Values, int Pattern, int StartIndex, int EndIndex)
		{
			if(StartIndex == EndIndex)
				return Values;
			//Pattern should be a bit string with a 1 followed by all 0's that represents the
			//Most significant digit to start at.

			int[] OriginalIndexes = new int[EndIndex - StartIndex];

			//Copy the array items we will be sorting to the temp array
			Array.Copy(Values, StartIndex, OriginalIndexes, 0, (EndIndex - StartIndex));
			int iZeroesCount = 0;
			for(int i = 0 ; i < OriginalIndexes.Length ; i++)
			{
				//Basic premise here is to throw all AND 1's right and all AND 0's left
				if((OriginalIndexes[i] & Pattern) == Pattern)
				{
					//It's an AND 1
					Values[EndIndex - (i - iZeroesCount + 1)] = OriginalIndexes[i];
				}
				else
				{
					//It's an AND 0
					Values[StartIndex + iZeroesCount] = OriginalIndexes[i];
					iZeroesCount++;
				}
			}

			//Call this function recursively twice - once for the 0's and once for the 1's
			int iNewPattern = Pattern >> 1;
			if(iNewPattern == 0)
				return Values;

			Values = MSDSort(Values, iNewPattern, StartIndex, StartIndex + iZeroesCount); // Sort the 1's
			Values = MSDSort(Values, iNewPattern, StartIndex + iZeroesCount, EndIndex);

			return Values;
		}
	}
}

So, not by much, but it does beat the Array.Sort. I verified the results with the IDE in debug mode before I rolled out the release mode for time testing.

[ICESTORM]

How come when using a separate routine for swapping as in

public static void Swap(ref int a, ref int b) {
int swp = a;
a = b;
b = swp;
}

It adds about +15&#37; to time (for QuickSort) it takes to sort when compared to putting the swapping code inside the Swap routine itself?

Is there a way to not make it slow down?

MSDRadix doesn't seem to be much of an improvement.
How does it compare to 3Way QuickSort?
Or this thing:
http://www.codeproject.com/KB/cs/fas...display=Mobile

^I think I remember trying that with Integers and it didn't work (result was still out of order).