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

[Marek Safar]

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 ?

Thanks
Marek

> Attached you'll find qsort.cs which includes 3 QuickSort implementations:
>
> 1. QuickSortBasic[R]: This is a basic QuickSort implementation and the 
> one currently in use as the sorting function in Array.Sort(). This 
> implementation always uses the middle element as the pivot.
>
> 2. QuickSortMedian[R]: This implementation is also a basic QuickSort 
> implementation which attempts choose a better pivot based on the 
> first, last, and middle elements. For sorted inputs and random inputs, 
> this seems to help performance somewhat as the array gets larger and 
> larger. However, for reverse-sorted inputs, it seems to kill 
> performance. Perhaps if I choose 3 random points to feed into Median() 
> it will do better.
>
> 3. QuickSortInsertion[R]: This implementation includes the above perf 
> trick and also includes an Insertion Sort fallback when partitions are 
> broken down smaller than some threshold # of elements (7 in the 
> attached code). It also falls back to Insertion Sort when it 
> encounters a worst-case scenario. As always, the performance 
> improvement with this is greater as the number of elements increases 
> and/or as the comparison function becomes more complex.
>
>
> You'll notice that the attached test program will print out the number 
> of comparisons that each sort routine uses in order to complete its 
> job. It's important to keep in mind that the more complex the 
> comparison function is, the more important it is that the number of 
> comparisons is kept to a minimum.
>
> Here are some example runs:
>
>
> [fejj at warpig sorting]$ mono ./qsort.exe -random 100000000
> Basic QuickSort comparisons needed:     3807986012
> QuickSort+Median comparisons needed:    3077915654
> QuickSort+Insertion comparisons needed: 3021355043
> Basic QuickSort finished in:     00:00:43.8178721s
> QuickSort+Median finished in:    00:00:37.3047443s
> QuickSort+Insertion finished in: 00:00:36.6122681s
>
>
> [fejj at warpig sorting]$ mono ./qsort.exe -sorted 100000000
> Basic QuickSort comparisons needed:     2632227866
> QuickSort+Median comparisons needed:    2632227867
> QuickSort+Insertion comparisons needed: 2483222808
> Basic QuickSort finished in:     00:00:21.8213618s
> QuickSort+Median finished in:    00:00:21.2622527s
> QuickSort+Insertion finished in: 00:00:19.0837352s
>
>
> (Note: I reduced the array size here due to wanting to head home for 
> dinner)
> [fejj at warpig sorting]$ mono ./qsort.exe -reversed 10000
> Basic QuickSort comparisons needed:     129546
> QuickSort+Median comparisons needed:    12522499
> QuickSort+Insertion comparisons needed: 39993
> Basic QuickSort finished in:     00:00:00.0016905s
> QuickSort+Median finished in:    00:00:00.0911385s
> QuickSort+Insertion finished in: 00:00:00.0008721s
>
>
> Jeff
>
>
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110406/d40e48ae/attachment.html