If it's worth saying, but not worth its own post, then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should start on Monday, and end on Sunday.
4. Unflag the two options "Notify me of new top level comments on this article" and "
It's an old problem, cousin_it has posted:
Radix. Except that it's not in place.
I know several reasonable algorithms for stable sorting in O(n log n) time and O(sqrt(n)) extra space, like Mrrl's SqrtSort. That's good enough for all practical purposes, because anyone who wants to sort a billion elements can afford an extra array of 30000 elements. And all known algorithms using less extra space essentially emulate O(sqrt(n)) bits of storage by doing swaps inside the array, which is clearly a hack.
Radix sort has its own rabbit hole. If you're sorting strings that are likely to have common prefixes, comparison sorting isn't the best way,... (read more)