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

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.

• "In this use case, the comparisons are the only amount of processing time that matters since it requires user input." - not sure what you mean, could you expand a bit? Specifically, what sort of user input, and in what format? Are the users just supplying the comparator function, or is there some more complicated logic involved? Also, have you verified the assumption that the number of comparisons is a good indicator of performance? Have you measured and compared the actual times for different implementations? Because the way you layout data may be more important due to cache (un)friendliness. Commented Oct 23, 2019 at 0:39
• The users click a button give two choices. The number of items won't ever exceed values great enough that a physical click will be faster than doing some data structure operations. Commented Oct 23, 2019 at 1:55
• I'm sorry if I'm being obtuse, but I'm just trying to better understand what you are trying to do - please be aware that we lack context other then what you provide in your question. You've given us a lot of info on your current train of thought, but not enough on the motivating problem. Your comment doesn't really answer any of my questions. I'm interested in what these two choices are (conceptually, in terms of their role in the application logic), and why do you think performance presents an issue at all. Not really sure what you were trying to say with your physical click remark. Commented Oct 23, 2019 at 2:13
• P.S. If you can provide more context - it's better to edit the question itself (and maybe just mention that you have done so in the comment section), so that people who didn't read the comments can get the additional info as well. Commented Oct 23, 2019 at 2:13
• P.P.S. "why do you think performance presents an issue at all" - more specifically; suppose you just put all the data in an ordinary array (or a similar structure continuous in memory), and just use a sort method from a standard library of your language to sort the whole thing every time, and not worry about using the most algorithmically efficient way to do it. What makes you think this wouldn't be a perfectly viable solution with good performance? (Furthermore, it might even perform better in practice then the alternatives.) Commented Oct 23, 2019 at 2:23

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).

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.

• I'm adding an optional 'required' checkbox for family and people who absolutely must be there to short-circuit those comparisons. I know that subjective comparisons are often contradictory, which is why I'm writing this tool. Commented Oct 22, 2019 at 19:57
• The UI is very simple, at least for the first version: just a text area with a simple syntax. Commented Oct 22, 2019 at 19:58
• @dx_over_dt - just wanted to add: there's a seed of a good idea here that you may be able to make use of. What you present to the user (the UI, the order of the items in the list, etc.) doesn't have to exactly map to the underlying representation; under the hood, you could maintain metadata about the list itself, store the sorted part and the new items separately, etc. - in order to have more control and organize the data in a way that lets you use the algorithm you prefer. Also, you can probably do a lot of that back and forth conversion client-side, and just send the quiz answers at the end. Commented Oct 23, 2019 at 23:05
• Ah, this is a one-page client app that'll be hosted on github pages. :) I think I'll just use insertion sort and state if the person's list is mostly sorted already, they should pick it, and stay away from quicksort Commented Oct 23, 2019 at 23:07