Worst-case performance of quickSort / getPivot

[Xinok]

On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei 
Alexandrescu wrote:
> On 11/16/13 11:46 AM, Xinok wrote:
>> * Regardless of these improvements, I think Timsort should be 
>> the
>> default sorting algorithm. It's the better choice in many 
>> (most?) cases
>> and, well, it's stable. Quick sort would still be available 
>> for those
>> cases in which it's faster and stable sorting isn't needed.
>
> There's something fishy about a more restricted algorithm doing 
> better than one that's less restricted. We must improve 
> unstable sort, not make stable sort the default.
>
> Andrei

Timsort is an "adaptive" sort. It's able to achieve better 
performance in many cases by exploiting patterns in the data.

I decided to make a nice little test using my benchmark code here:
https://github.com/Xinok/XSort/blob/master/benchsort.d


This is the permutation I designed for the test:

static uint[] base;
base.length = 1024 * 1024;
foreach(i, ref v; base) v = i;

foreach(i; 0..1024)
{
	auto rand()
	{
		rndGen.popFront();
		return rndGen.front % base.length;
	}
	
	switch(rand() % 3)
	{
		// Swap two ranges of elements
		case 0:
		{
			auto arr = [rand(), rand(), rand(), rand()];
			sort(arr);
			swapRanges(base[arr[0]..arr[1]], base[arr[2]..arr[3]]);
		} break;
		
		// Reverse a range of elements
		case 1:
		{
			auto a = rand(), b = rand();
			if(a > b) swap(a, b);
			reverse(base[a..b]);
		} break;
			
		// Shuffle a small range of elements
		case 2:
		{
			auto a = rand();
			while(a < 1024) a = rand();
			assert(a >= 1024);
			randomShuffle(base[a - 1024 .. a]);
		} break;
			
		default: assert(0);
	}
}


And the results (last number is predicate calls):

Current Unstable Sort  50ms  32783474
New Unstable Sort      69ms  21503542
Timsort                35ms  3905887


That's why I suggest making Timsort the default sorting algorithm.