Suppose you want to sort your movie collection, from favorite to hated. You apply the rules of some sorting algorithm by asking many questions of the form: "Did I like A or B more?"

It's now sorted, right? Logically, every necessary question was asked to prove that when index(A) < index(B), A > B. But you can show that this is false for at least one pair A and B. Surely, the algorithm should have asked more questions.

Opinion is hard to nail down, and if one comparison is off, the whole sorting operation might result in something way off.

Which sorting algorithm would you pick to ensure the sorted list won't be too impacted by a bad comparison?

  • 2
    Entire books have been written about this soft of thing. Do you have a more specific question? Nov 17 '15 at 2:05
  • 1
    While your question hasn't been closed, you might want to read Why was my question closed as primarily opinion-based? Nov 17 '15 at 2:05
  • Was not aware this "error-tolerant sorting" was a common problem in CS. And regarding opinion-based: I'm not sure where else I would have put this, if SO and Programmers both have policies against opinion-based. Nov 17 '15 at 2:11
  • 2
    This is one of the more interesting questions I've read on here in a while. While at face value it seems rather boring, there are a lot of potential use cases for this - especially if you are basically using any heuristic to evaluate A > B types of questions. Can you edit to clarify at least one example for when a common sort fails with a single opinion mistake? That would help clarify significantly.
    – enderland
    Nov 17 '15 at 2:40
  • Agree with @enderland, its an intriguing question and would like to see more about the failure cases - you never know when this will help in your future code writing. Now a favorite question.
    – miltonb
    Nov 17 '15 at 5:11

The key thing here is to avoid making the same comparison more than once. And there is one sort that really meets that criteria in a way that is doable for a human sorting their movie collection.

Merge sort.

With the merge sort, you recursively break down the size of the set to 2 (or 1). And then you sort each of those. Now, you take two sets of 2 (the actual algorithm takes it down to sets of 1, but we're doing this by hand and so can avoid that level of exactness), and then compare the first element of each, of those. If you have 36 and 24 - you have already compared 3 and 6, you aren't going to compare them again. The resulting set then becomes 2346 and then you continue on merging with the next set of four.

From the wikipedia page:

The key here is that with each comparison, you are not reevaluating the previous comparisons. Thus, if you decide that you like the Yellow Submarine more than the Hard Days Night once, you are not going to re-evaluate that and they aren't going to end up too far from each other in the end.

The problem with many other sorts is that you are either constantly asking "do I like this more than Santa Claus Conquers the Martians" each time with a selection / insert / bubble sort. And other sorts become far too complicated to be able to reason about.

A way to test this that would make for some very interesting blog posts is to implement the different sorts yourself and override > or compareTo in your chosen language. In that method, add a slight bit of randomness to it, say, +/- 10% of the value. or +/- 1% of the value.

Then, sort the numbers 1 .. 100 100x and see how far out of whack each sorting method results in.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.