Radix sort wouldn’t allow for the “possible to sort any other data type” part.

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.

Exactly. It has the same limitations as a radix sort, which is why I find them comparable

For a radix sort it’s impossible to sort linked data structures, at least as I understand it.

Whereas any comparison based sort can follow the pointers and do arbitrary comparisons.

In the source code, it is not apparent where the size restriction comes from. It seems to me that it can be easily modified to work with any data types. Maybe I am wrong. I am more concerned with this sentence:

> 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?

Is the included bench.c the right way to answer that question?

  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.102616

It is, those numbers are less favorable than they are on my own machine.

The speed of your RAM memory is likely to have an influence on performance. My system is running at 2133MHz.

Interesting.

  16 GB 2133 MHz LPDDR3

Built with Apple clang version 12.0.5 (clang-1205.0.22.11) gcc -O3 bench.c

Blitsort can sort strings, but something like a 12 byte data structure would require an array with pointer references to sort.

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 am thinking more about sorting, say, 20-byte or 24-byte custom structs. Directly sorting arrays is probably faster than sorting pointers to arrays. At least in my applications, I rarely just sort numbers; I more often sort numbers along with other data associated with the numbers.

Hard to say which would be faster, I've made a mental note to benchmark sorting 16 byte long doubles through pointers as well as directly.

I never tried, but it should be possible (and relatively easy) to add custom sizes in the .h file.