Radix sort has a lot of issues and is less than flexible. I've briefly considered Heap sort, but as in the case of Merge sort, there is the question of a memory complexity that increases with the count. Since I was looking for optimizations on the million item level, I've decided to go with the one that does in-place sorting.
I thought of the idea of using Quick and default based on some measurement, but in my case I didn't know what the size of the iterable was and even if I did, I am losing performance with small counts and gaining performance on large counts. Seems to me I can safely ignore small count performance anyway.
What I liked about Quick sort is that I can do .skip, .take, .skipLast and .takeLast operations on an ordered enumerable only when I am actually iterating the result. In that case, I need to perform a Quick sort only to take items from a start to an end index. This allows me to ignore sorting partitions outside that range. I don't know if it would have worked just as well with Merge sort and I didn't see the point of using Merge sort and compete with the Merge sort implementation in Firefox and Safari.
Radix sort has a lot of issues and is less than flexible. I've briefly considered Heap sort, but as in the case of Merge sort, there is the question of a memory complexity that increases with the count. Since I was looking for optimizations on the million item level, I've decided to go with the one that does in-place sorting.
I thought of the idea of using Quick and default based on some measurement, but in my case I didn't know what the size of the iterable was and even if I did, I am losing performance with small counts and gaining performance on large counts. Seems to me I can safely ignore small count performance anyway.
What I liked about Quick sort is that I can do .skip, .take, .skipLast and .takeLast operations on an ordered enumerable only when I am actually iterating the result. In that case, I need to perform a Quick sort only to take items from a start to an end index. This allows me to ignore sorting partitions outside that range. I don't know if it would have worked just as well with Merge sort and I didn't see the point of using Merge sort and compete with the Merge sort implementation in Firefox and Safari.
It looks like there are not a lot of algorithms for partial sorting. But you could see the C++ implementation that uses Heapsort
github.com/gcc-mirror/gcc/blob/d93...