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

[Dawid Weiss]

Just out of curiosity, have you compared against a
mergesort/insertionsort combination? Java uses merge sort for object
sorting and taking into account cpu caches, merge sorts are really
competitive to qsort these days.

Also, there is a bunch of improvements to plain mergesort, as in
timsort for example:

http://en.wikipedia.org/wiki/Timsort

Dawid

On Sun, Apr 10, 2011 at 3:35 PM, Jeffrey Stedfast <fejj at novell.com> wrote:
> On 04/09/2011 04:39 PM, Jeff Stedfast wrote:
>
> 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
>
> Just to be clear, I meant "how do you feel about *me* doing the work to
> replace the current QuickSort impl in corlib with mine?" :-)
>
> I just want to make sure before I create a patch that people are interested.
>
> That said, I forgot to include benchmark results:
>
> [fejj at serenity sorting]$ mono ./qsort.exe -random 10 10000000
> BasicQuickSort comparisons needed:     430000000
> FasterQuickSort comparisons needed:    250000000
> BasicQuickSort finished in:            00:00:18.8535031s
> FasterQuickSort finished in:           00:00:16.4478594s
>
> [fejj at serenity sorting]$ mono ./qsort.exe -sorted 10 10000000
> BasicQuickSort comparisons needed:     330000000
> FasterQuickSort comparisons needed:    180000000
> BasicQuickSort finished in:            00:00:16.9532771s
> FasterQuickSort finished in:           00:00:14.1202212s
>
> [fejj at serenity sorting]$ mono ./qsort.exe -reversed 10 10000000
> BasicQuickSort comparisons needed:     360000000
> FasterQuickSort comparisons needed:    180000000
> BasicQuickSort finished in:            00:00:17.4450895s
> FasterQuickSort finished in:           00:00:15.1590930s
>
>
> Jeff
>
>
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>