[Mono-dev] Possible QuickSort optimizations for Array.Sort()

[Jeffrey Stedfast]

On 04/06/2011 03:18 AM, Marek Safar wrote:
> Hello,
>
> >>>
> 	public class Sort<T>  {
> 		public delegate int Comparison (T v0, T v1);
>
> You don't need yet another delegate, just use standard Func
>
> >>
> 		static readonly int INSERTIONSORT_THRESHOLD = 7;
>
> Why not to used const int ?
>
> More importantly what is performance of sorting array of 10-20 
> elements called 1000000 times ?
>

Attached is another test program with 2 newer/faster implementations of 
QuickSort, one of which is Non-Recursive.

You can run this program like so:

mono ./qsort.exe [-random, -sorted, -reversed] [array size] [# loops]

These 2 new implementations manage to reduce the number of comparisons 
done by merging the Median() function from the previous set into the 
main body of the QuickSort function and swapping those 3 elements into 
ascending order as it compares to find the optimal pivot. This has the 
advantage of allowing our loops to start at low+1 and high-1 (thus 
reducing our compares by 2 for each partition).

My previous implementation was able to reduce the compares by 1 by 
starting at low+1 by moving the pivot into low, but this has the 
negative impact of destroying performance on reverse-sorted arrays. My 
new implementation doesn't have this problem (and therefore, we don't 
need to fall back to that insertion-sort if we detect that pathological 
case).

Interestingly, the NonRecursiveQuickSort() implementation does not 
noticeably improve performance over the recursive version and in fact is 
slower than even our current implementation for sorting small arrays 
(made evident when looped millions of times).

How do you feel about replacing corlib's qsort() implementation with my 
FasterQuickSort() implementation?

Jeff

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110409/80b31484/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qsort.cs
Type: text/x-csharp
Size: 8709 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110409/80b31484/attachment-0001.bin