Minimal k-way comparison sorting algorithm?

Question

I've watched 600 TV shows, and I want to sort them in order of how much I liked them. I'm bad at assigning absolute scores, but good at comparing relative enjoyment, so it has to be a comparison sort. But even with an optimal algorithm, a comparison sort based on pairwise comparisons on 600 elements would take thousands of comparisons.

That would probably only take a couple hours, but I thought having each comparison be in batches of k (=, say, 5) items at a time would be faster. I think I can rank 5 things pretty quickly. The program would calculate which items to compare and show me them, and I would just drag them around, submit, and repeat.

I don't know much about information theory, but I assume since each comparison has k! outcomes (one for each permutation), it should only take log_{k!} (n!) comparisons to sort n items, which, for n=600, k=5, is under 680.

Is there any algorithm designed for this? The closest I've found is the k-way merge, but that would only use the k-way comparison at the very start. I think a recursive Ford-Johnson-style algorithm might work, but I don't know.

Also, if this is useful, I've already scored most of the TV shows on an integer scale from 1 to 10, but that's not nearly enough granularity to sort with, and it's a very loose scoring, too; arbitrarily, only score differences greater than 2 are valid (e.g. a 4 may be better than a 6, but is definitely worse than a 7). Almost all the scores are 7.

Answer 1

If you need to give the comparisons beforehand, you unfortunately need n^2/2 comparisons, because if items x and y are consecutive after sorting, you must have compared them. On the other hand you should have items that are so very different that they cannot be consecutive.

You could give a rough rating with the understanding that any two items that are very different according to the rating can be compared with the rating alone. And only ratings close together would require another comparison. For example if you have ratings of 50 and 52 the ratings can be inaccurate and the 50 rated is actually better. If they are rated 50 and 70, the second might in reality not be quite as good but will still be better than the first.

Now with something like TV shows there is the question whether they can be meaningful compared at all. How would you compare say a horror movie and a comedy, when they are just too different? You can have situations where A is better than B, B is better than C, yet C is better than A.

Answer 2

It appears there are papers in the research literature that tackle the problem of sorting with multiway comparisons. See, e.g.,

An Enhanced Multiway Sorting Network Based on n-Sorters.
Feng Shi, Zhiyuan Yan, Meghanad Wagh. arXiv:1407.0961.

I haven't tried to understand the paper, so I'll let you read the paper and find related literature (e.g., by using Google Scholar to find other papers that cite this paper).

---

I will suggest a heuristic for your problem that might be good enough, particularly if you think you are perfect at rating (you never make inconsistent ratings):

1. Build a directed graph, with an edge $a \to b$ if you have rated show $b$ as better than show $a$.

2. Find a topological sort of the graph, e.g., using Kahn's algorithm. (In the first round, before you have done any comparisons, you can sort them by the absolute rating.)

3. Let $s_1,\dots,s_n$ be the shows, in this topologically sorted order. Now put shows $s_{5i+1},s_{5i+2},s_{5i+3},s_{5i+4},s_{5i+5}$ together in a batch, for each $i$.

4. Compare each batch. Add edges to the directed graph (each batch of 5 adds ${5 \choose 2} = 10$ edges to the graph).

5. Go back to step 2.

Alternatively, another possible heuristic would be to use a rating system, such as Elo. For instance, initially assign each show an Elo between 1000 to 2000 based on your absolute rating. Then, sort the shows by Elo (or you can add a random number to each Elo and then sort by randomized Elo), resolving ties arbitrarily. Construct batches from each set of 5 adjacent shows in this sorted order. Compare within each batch, and then for each pair of shows in the same batch, update those show's rating using the Elo rules. Repeat for several rounds until the Elo converges.

I don't know how well these will work, and I don't know whether there are algorithms designed for the specific problem you've asked about. These are just some ideas for your consideration.