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

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

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

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