Blitsort is an in-place stable adaptive rotate merge sort

Re:Blitsort is an in-place stable adaptive rotate merge sort by scandum on Saturday July 10, 2021 @01:22PM (#27794964)

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.

[ Parent | on HN ]

Re:Blitsort is an in-place stable adaptive rotate merge sort by acmj on Saturday July 10, 2021 @03:29PM (#27795809)

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.

[ Parent | on HN ]

Re:Blitsort is an in-place stable adaptive rotate merge sort by scandum on Saturday July 10, 2021 @04:14PM (#27796121)

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.

[ Parent | on HN ]