Blitsort supports long doubles and 8, 16, 32, and 64 bit data types. By using 32 or 64 bit pointers it's possible to sort any other data type.
Seems quite limited, wonder how it compares to radix sort.
Seems quite limited, wonder how it compares to radix sort.
I do wonder about not enabling inlining structs. I don’t know where the crossover happens, and it certainly varies with hardware characteristics, but I’m sure a data structure made up of say an int and two longs would better be sorted in contiguous memory rather than as an array of pointers to random places in the heap.
Whereas any comparison based sort can follow the pointers and do arbitrary comparisons.
> Blitsort's performance is similar to that of quadsort as long as the auxiliary memory is greater or equal to the square root of the array being sorted, which comes out at 262,144 elements with the default stack of 512 elements. Performance on larger arrays degrades marginally.
I wonder what "marginally" means here. What if we sort 10 million integers?
1m random dist size 128 avg qsort 0.206549 blitsort 0.281630
10m random dist size 32 avg qsort 2.963479 blitsort 4.394143
100m random dist size 128 avg qsort 34.996847 blitsort 54.102616The speed of your RAM memory is likely to have an influence on performance. My system is running at 2133MHz.
16 GB 2133 MHz LPDDR3
As for the degradation against std:stable_sort:
5% slower at 1 million, 10% slower at 10 million, 20% slower at 100 million.
With sqrt n auxiliary you're looking at 2%, 4%, 6% slower.
Against qsort() it remains faster at 10 million, 3% slower at 100 million.
I never tried, but it should be possible (and relatively easy) to add custom sizes in the .h file.