Tried implementing compile-time sorting with old-school TMP (recursive templates, no constexpr). Yeah, constexpr sort exists now, but I wanted to see how far pure template recursion could go. Quicksort and mergesort worked fine. Heapsort was the one that broke.
Then it clicked: heapsort assumes cheap random access. Parent node, left child, right child, all index arithmetic. But in a typelist like
arr<5, 3, 8, 1> there's no arr[i]. Every element access peels the head off recursively, so it's O(n) per lookup. Heapify becomes expensive, sift-down becomes expensive, and the whole thing degrades.What I actually ended up with was... selection sort. Find the min by scanning the whole list, pull it out, recurse. O(n²) template instantiations. Not great.
Quicksort doesn't have this problem because it just filters into two sublists (less-than pivot, greater-than pivot). No indexing needed. Mergesort splits with take/drop which is O(n) but only happens once per level, so it stays O(n log n) overall.
I didn't really clock the random access dependency until I was halfway through writing the heap version. Felt kind of dumb in retrospect. Never really felt how much big-O depends on the data structure until TMP took away my arrays.
Full code in comments if anyone wants to look at it. Fair warning the mergesort lives in
namespace www because I was iterating on these in separate files and never bothered renaming.Anyone else run into algorithms that stop making sense in TMP?
https://redd.it/1syqjdu
@r_cpp
