🤔 scry sort
- (based on work done in 2017-09-22)
- a best-worst-case minimal-comparison comparison sort algorithm
- the algorithm
- setup
- given input list, generate a set of all possible sortings (N!)
- also generate a list of possible comparison pairs (0 v 1, 0 v 2..., 1 v 2 ...) (n(n+1)/2) (Nc2)
- the loop
- pick a pair from the list such that results would split the possible sortings evenly
- the result of a comparison eliminates many of the possible sortings
- to achieve the best worst case, we want the split to be as even as possible (maximize information gained in the worst case)
- ie. a > b would result in # of remaining sorts ~= to b > a
- in the event of a tie, pick first pair (to force determinism)
- decrease the set of all possible sortings, and remove the chosen pair from the list
- repeat
- questions:
- is the greedy approach optimal?
- (ie. should we consider future steps and their potential splits)
- probably no?
- is there a better tie-breaker?
- there will be lots of pairs to choose with identical one-step splits
- but, multiple steps deep, there are some choices better than others
- the optimal algorithm would also be "the ultimate cheat"