Sort or data structure with fewest comparisons if list is mostly sorted

Question

Suppose you have a list of about 50 items that are already sorted and you add three items either to the end of the list or somewhere unsorted into the middle. Now you want to re-sort the list with the fewest possible comparisons. Which sorting algorithm or data structure would you use?

---

Context

I'm writing an online sorter app where the comparisons are subjective. Consider the case where you want to figure out who to invite to your wedding given n (e.g. 200) people and m < n (e.g. 100) seats. You want a way to find the top m most important people to invite.

After entering their data into a <textarea>, I generate a "quiz" that prompts them with two item buttons, asking which is more important. The sorting algorithm uses that input as the comparison. I want to minimize the length of the quiz.

In this use case, the comparisons are the only amount of processing time that matters since it requires user input. The actual sorting of such a small number of items happens behind the scenes in a fraction of a second, so no matter how inefficient it is, it won't compare to the time spent comparing two people/families.

I've discovered for thoroughly shuffled lists, an AVL-tree (with memoized comparisons) is actually the most efficient, despite being one of the least efficient self-balancing trees in the real world. For 58 items, it beats Quicksort by an average of 17 comparisons and merge sort by 73.

Suppose the user sorts their list and then remembers three people they forgot to add. Their input is now sorted, but rather than doing what they probably don't know is an insertion sort, they just add the items to end of their list and click the sort button again. At this point, we don't know that their list is mostly sorted, nor that only the last three items are new, so we can't do an insertion sort ourselves. I give options and descriptions for various sorting algorithms so they can choose which algorithm will be most efficient for them. For unsorted lists, the AVL tree algorithm is best. For "mostly sorted" lists, I'll present another algorithm option.

Ideally, if the list is already sorted, it will require exactly n-1 comparisons. If there are 3 unsorted items, it will require 3n comparisons in the worst case, and ~3n/2 on average, assuming the items belong in the middle of the list.

My instinct says bubble sort--another unlikely algorithm--would be best for my scenario, but I don't know enough about the numerous sorting algorithms to be sure. (I could also be wrong about insertion sort being impossible/inefficient.)

---

This project is largely done now. I might go back and implement Timsort to see how it compares, but for now, I've just used Insertion Sort. When I said we couldn't use Insertion Sort above, I was thinking of Selection Sort.

The project can be found at https://dfdx.us/subjective-sorter.

Answer 1

Suppose you have a list of about 50 items that are already sorted and you add three items either to the end of the list or somewhere unsorted into the middle. Now you want to re-sort the list with the fewest possible comparisons. Which sorting algorithm or data structure would you use?

Definitely Timsort, which was designed exactly for this situation.

But your problem is different. When the user entered a < b, then comparing a and b is free as there's no need to ask them again. Similarly, when the entered a < b and b < c, then you should infer a < c and don't bother them. Your intermediate result is not a mostly sorted list, but it's the set of already obtained answers.

So you need to compute the transitive hull and look what is the minimum number of arrows to add in order to produce a total order. Transitive hull, even updated incrementally is simple, but finding the minimum is probably hard.

Maybe you could proceed like merge-sort as it produces even longer sorted sequences, which are easier to think about than some arbitrary partially sorted sets. When merging lists of unequal sizes (like after adding a forgotten person), you'll should make comparisons with middle elements first (binary-search-like).

Update

I guess, the comparison you should ask for is always the one giving the maximum transitive arrows. This corresponds with my above note about "comparisons with middle elements".

As the number of transitive arrows for a given question a ≷ b can be computed as the product of the product of number of elements less than a and greater than b or the other way round, depending on the response. You should probably use the minimum of the two or maybe some weighted average.

When you keep track of how many smaller and greater elements exist for each element, then you can do this with some O(n²) operations (which is a lot, but it's not the computation time what you're striving to minimize).

Answer 2

At this point, we don't know that their list is mostly sorted, nor that only the last three items are new, so we can't do an insertion sort ourselves.

Why not? That seems like it would be relatively easy data to include, but I don't know your architecture.

You could also try to solve this from a UI perspective, with a path for adding new items to a sorted list and a separate path for re-sorting a list entirely. I don't know enough about UX or your user base to say whether or not that's a good idea, but it's an option to try.

One other thing to consider (that might be a bit too broad) is whether or not users will be able to accurately sort people this way. I know that it would be difficult for me to provide a total order for my friends and family, so the minimal number of comparisons might result in a worse experience. Having redundant (and possibly contradictory) comparisons would be more difficult to sort, but might make a more useful tool.