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

[Jeffrey Stedfast]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: qsort.cs
Type: text/x-csharp
Size: 7895 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110405/bee0a775/attachment.bin