For example, suppose you have a list of about 50 items that are already sorted, and you add three items either at the bottom of the list or at an unsorted midway point. Now you want to reorder the list with as few comparisons as possible. Which sorting algorithm or data structure would you use?

**context**

I am writing an online sorter app in which the comparisons are subjective. Consider the case in which you want to find out who you want to invite to your wedding `n`

(eg 200) persons and `m`

< `n`

(eg 100) seats. They want a way to find the top `m`

most important people to invite.

In this use case, the comparisons are the only important processing time because user input is required. The actual sorting of such a small number of elements takes place within a fraction of a second behind the scenes. Regardless of how inefficient the sorting is, it is not compared to the time spent comparing two persons / families.

I have found for thoroughly mixed lists that an AVL tree (with stored comparisons) is indeed the most efficient, although it is one of the least efficient self-balancing trees in the real world. For 58 elements it beats Quicksort by an average of 17 comparisons and merges the sort order by 73.

Suppose the user sorts his list and then notes three people he forgot to add. Your inputs are now sorted, but instead of doing what they probably do not know is a paste sort, just add the items to the bottom of their list and click the Sort button again. At this point, we do not yet know that the list is mostly sorted or that only the last three elements are new. Therefore, we can not do any insertion sorting ourselves. I specify options and descriptions for various sorting algorithms so they can choose which algorithm is most efficient for them. For unsorted lists, the AVL tree algorithm is best suited. For "mostly sorted" lists I introduce another algorithm option.

If the list is already sorted, ideally this is what is needed `n-1`

Comparisons. If there are 3 unsorted elements, this is required `3n`

Comparisons in the worst case and `~3n/2`

on average, assuming that the elements belong in the middle of the list.

My instinct says Bubble Sort – another unlikely algorithm – would be best for my scenario, but I do not know enough about the numerous sorting algorithms to be sure. (I could be wrong too if the paste is impossible / inefficient.)