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.
Nice. If you have only integers for keys you may consider Radixsort however it's not stable.
Or you could check the size of the array and if it's less that 42 you could leave the default sort but it it's more that 42 you could use quicksort.
Or you could just use MergeSort if you can live with the O(n) space complexity.
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...