So since this sorting algorithm involves a trie, would there another optimization possibility by using a data structure inspired by the MergedTrie?<p>My first thought would be to split the list of numbers into a prefix and a suffix part and building two tries connected at the leaves[1][2], replacing the trie used in the article. Then we sort both tries using the Kirkpatrick-Reisch method (but in reverse order for the suffix trie so that the final result is sorted correctly), and finally we would have to reconnect the two while walking the tries.<p>[0] <a href="https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0215288" rel="nofollow">https://journals.plos.org/plosone/article?id=10.1371/journal...</a><p>[1] more or less, the MT in the linked paper works a bit differently but also has a different use-case in mind.<p>[2] Also I have no idea if it make sense to have two depth 2 tries, or if there is <i>another</i> algorithm out there with two depth 1 tries that _kind_ of looks like this algorithm
I suspect memory indirection would clobber the theoretical perf, but I'd be happy to be proved wrong.<p>My inclination is that this would be slower than "standard" high perf radix sorting, but I'm not sure if the high level overview of this algorithm represents an equivalent level of implementation.
If you are into integer sorting, this might be of interest as well:<p><a href="https://yourbasic.org/algorithms/fastest-sorting-algorithm/" rel="nofollow">https://yourbasic.org/algorithms/fastest-sorting-algorithm/</a><p><a href="https://sorting.cr.yp.to/" rel="nofollow">https://sorting.cr.yp.to/</a>