[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

It was just a quick hack to get things going, if we decide it's worth 
having corlib move to my QuickSort implementation, it would use the same 
standard func corlib is using now.

> >>
> 		static readonly int INSERTIONSORT_THRESHOLD = 7;
>
> Why not to used const int ?

I never learned when to use const vs static/readonly in C# :-(

I assume you suggest const because it is more appropriate, so I will :-)

>
> More importantly what is performance of sorting array of 10-20 
> elements called 1000000 times ?


I've attached a sample program to test this in case you'd like to play 
with it some more, but here are the results on my system for 20 elements 
@ 1 million iterations:

[fejj at serenity sorting]$ mono ./qsort-small.exe -random 1000000
Timings for sorting 20 random items 1000000 times.
Basic QuickSort finished in:     00:00:03.0227324s
QuickSort+Insertion finished in: 00:00:02.5357660s

[fejj at serenity sorting]$ mono ./qsort-small.exe -sorted 1000000
Timings for sorting 20 sorted items 1000000 times.
Basic QuickSort finished in:     00:00:02.3003898s
QuickSort+Insertion finished in: 00:00:01.9493073s

[fejj at serenity sorting]$ mono ./qsort-small.exe -reversed 1000000
Timings for sorting 20 reversed items 1000000 times.
Basic QuickSort finished in:     00:00:02.4001482s
QuickSort+Insertion finished in: 00:00:02.3277809s


And here are the results for 10 elements @ 1 million iterations:

[fejj at serenity sorting]$ mono ./qsort-small.exe -random 1000000
Timings for sorting 10 random items 1000000 times.
Basic QuickSort finished in:     00:00:01.8165901s
QuickSort+Insertion finished in: 00:00:01.7363410s

[fejj at serenity sorting]$ mono ./qsort-small.exe -sorted 1000000
Timings for sorting 10 sorted items 1000000 times.
Basic QuickSort finished in:     00:00:01.7398261s
QuickSort+Insertion finished in: 00:00:01.5270049s

[fejj at serenity sorting]$ mono ./qsort-small.exe -reversed 1000000
Timings for sorting 10 reversed items 1000000 times.
Basic QuickSort finished in:     00:00:01.7166351s
QuickSort+Insertion finished in: 00:00:01.6798535s


Hope that helps,

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