inventing a sorting algorithm with as few comparisons as possible for k-ary sorters?
I want a comparison sort where the human does the comparison (so all other operations take essentially 0 time relatively). I have 900 things to sort (I'm ranking shows I've watched), so binary comparisons would take a long time (~7541 comparisons). If we instead use k-ary comparisons (computer shows me k=10 at a time and I rank each batch individually), then, theoretically, we could get down to only log(900!)/log(10!)=~347 10-way comparisons!
I've looked around, but there doesn't seem to be much research on the topic. So I thought of a simple idea: just do binary insertion sort, but include other, unsorted elements in each comparison as well. That way, when we later go on to insert those unsorted elements, we already have a bit of an idea of the range they can be inserted in.
You can see a demonstration of my idea for k=3 in this video: https://x.com/JentGent/status/2056809963625078974
(I tried to insert them in alphabetical order to make the demonstration clearer, but I accidentally went out of order for some of the items.)
How would you implement this in practice? Right now, I'm updating the whole directed graph with a DFS on every node for each comparison, which I guess is fine if I say all operations except comparison take negligible time, but there's surely a more elegant solution. I've also faced some interesting edge cases that might complicate an implementation. Ideally, you should never know beforehand the order of any two pairs of elements in any k-way comparison you make, but it seems that's sometimes not possible