# A sorting algorithm that uses the minimum comparasions possible

I'm looking for a sorting algorithm that minimizes comparisons instead of time complexity.

The algorithm shouldn't compare any two elements for which the relation between them can be derived from comparisons previously made. For example, given three elements $$A$$, $$B$$, and $$C$$ such that $$A, the algorithm shouldn't attempt to compare $$A$$ to $$C$$ if it already compared $$A$$ to $$B$$ and $$B$$ to $$C$$. (Of course, if the algorithm compared $$A$$ to $$B$$ and then $$A$$ to $$C$$, it would then also need to compare $$B$$ to $$C$$. That's okay.)

Since sorting algorithms have been studied for decades, I'm guessing there already exists an algorithm for this.

My use case is allowing a user to sort things by preference by showing two of those things side-by-side.

• Do you care about the exact minimum (from your use case, sounds like probably not, but it's good to check), or just something "good enough"? Exact minimum is a complicated story, and is only known for sorting lists up to length 24 or so. – Joshua Grochow Feb 10 at 16:31

Using simple methods, it can be shown that any comparison-based algorithm must perform at least $$n\log{n}-o(nlogn)$$ comparisons. This bound is obtained (up to lower terms) by the binary insertion sort algorithm (see e.g. [1] for a good introduction on the topic). There are also many other algorithms which obtain this bound asymptotically up to a constant factor, e.g quicksort (in expectation) and heapsort.
• Though, frankly, the whole setup sounds quite weird. Instead of asking $n\log n$ binary questions, why don’t you simply ask the user “rank these $n$ items according to your preference”? Given them an interactive list where they can move the items around. This also avoids another problem (or rather, shifts it to the user), namely that users’ binary choices most likely will not form a linear order, but a nontransitive tournament, so if you ask for $A<B$ and $B<C$ and infer $A<C$, the user will complain that they actually prefer $C<A$. – Emil Jeřábek Feb 11 at 7:20