Sorting algorithm

[Xinok]

On 10/7/2011 2:27 PM, Ellery Newcomer wrote:
> tinkered with timsort a bit a few months ago. comparing that to your
> sort, I get numbers like
>
> xinokSort
> random: 77   ascending: 0   descending: 21
>
> timsort
> random: 354   ascending: 1   descending: 4
>
>
> where each are sorting a 500k element array of int, times are msecs,
> compilation flags were -O -inline -release, sources are
>
> http://personal.utulsa.edu/~ellery-newcomer/timsort.d
> http://personal.utulsa.edu/~ellery-newcomer/xinokSort.d
>
>
> Nice job, Xinok.
>
> anyone want to try to optimize my timsort? :)

The benchmark for descending is no surprise since timsort explicitly 
searches for runs in descending order. However, the random benchmark 
isn't what I expected. My sort is a bit slower than a standard merge 
sort, so I would expect Timsort to be faster.

While part of the reason may be your code is unoptimized, it may also be 
the fault of a bug. I ran some more benchmarks and I found a few cases 
where your code failed, specifically when the data is mostly random. 
Just a guess, but your code may have a problem when the "runs" are too 
small.

I also found a case when std.algorithm.sort performs poorly, under Small 
Shuffle + Descending.


Numbers represent time taken; Smaller numbers are faster
An MD5 hash is generated for each sort, to verify it was sorted correctly
phoboSort is unstable std.algorithm.sort

Ascending
Is length: 16777216
xinokSort: 50722        C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 726046       C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 943475       C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 1778944      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 3082901      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 955285       C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 89201        C8B8D3A2B4D9882ABCFC31721EF27145


Descending
Is length: 16777216
xinokSort: 1916452      C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 2238446      C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 1581095      C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 3390033      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 3067271      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 1035827      C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 240896       C8B8D3A2B4D9882ABCFC31721EF27145


Complete Shuffle
Is length: 16777216
xinokSort: 7607511      C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 8814887      C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 5623837      C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 6704733      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2825567      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 5532275      C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 29142913     E03C4778321F69D8AD10F624E6093599


Small Shuffle (1024 pairs were picked at random and swapped)
Is length: 16777216
xinokSort: 589882       C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 3651222      C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 2655391      C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 2162840      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2988630      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 963103       C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 6523251      C8B8D3A2B4D9882ABCFC31721EF27145


Large Shuffle (1,048,576 pairs were picked at random and swapped)
Is length: 16777216
xinokSort: 1956126      C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 7617207      C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 3089674      C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 2606200      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2932306      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 1619484      C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 14883251     DE54E94D1A058459FEA3A80096FCBB18


Small Shuffle + Descending
Is length: 16777216
xinokSort: 2288869      C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 4599417      C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 2604222      C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 3457241      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 3055080      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 261768564    C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 10149160     C8B8D3A2B4D9882ABCFC31721EF27145


Large Shuffle + Descending
xinokSort: 2923813      C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 7678966      C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 3833138      C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 3971124      C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2941206      C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 3749512      C8B8D3A2B4D9882ABCFC31721EF27145
tim  Sort: 22709918     191BD30B3D0E52C922A7E6A16E5E63A5