Alternatives to TPIE : Radix Sort and Radix Heap

[SSoelvsten]

Similar to #199 , we may want to investigate whether a radix sort on the keys can out-compete

Radix Sorting

• [ ] Solve parts of #445 such that there is a read-write iostream<T> class.
• [ ] Implement an Internal Memory radix_sort<T, Key> where Key provides the logic to get the sorting key as an integer.
• [ ] Implement an External Memory radix_sort<T, Key>.
• [ ] Rename the sorter<T, Comp> to comp_sorter<T, Comp>
• [ ] Use radix_sort<T, Key> wherever possible.

2-ary and 3-ary keys (i.e. the product construction algorithms) may need some extra thinking to both be primarily sorted on the first to-be seen value and also group all requests together.

Radix Heap

For Dijkstra's algorithm, people have proposed a Radix Heap. This may also be useful here too; especially if it also is tuned for the cache and the RAM at the same time (see also #677). Notice, that the cross-level priority queue indeed is monotone. Yet, the per-level priority queue is not.

The radix-based prefix-trie for Burstsort may also be repurposed for a priority queue.

Additional Context

The Radix Sort was suggested by Riko Jacob. I added the Radix Heap, as it seems related.