<p>Using simple methods, it can be shown that any comparison-based algorithm must perform at least <span class="math-container">$n\log{n}-o(nlogn)$</span> 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.</p>
<p>That said, for practical purposes I suggest you use the sorting algorithm already implemented in your prefered programming language, as it is most likely been highly optimized, and would work faster than if you implement it yourself, unless you have a very specially structured input.</p>
<p>[1] <a href="https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.79" rel="nofollow noreferrer">https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.79</a></p>

CC BY-SA 4.0
2021-02-10T18:28:35.557Z
Since asking the user is an asynchronous operation, using the built-in sorting algorithm in JavaScript is not possible. Binary insertion sort sounds like a good idea.
D. Pardal
CC BY-SA 4.0
2021-02-10T19:13:21.903Z
I'm not sure I follow, but if you wish to implement the sorting algorithm yourself, you might want to consider quicksort as (a) it is very fast in-practice (b) it is very easy to implement, and (c) it works very well with CPU caching (though I am not an expert in the subject of in-practice sorting algorithms)
user3209423940248
CC BY-SA 4.0
2021-02-10T22:36:43.613Z
Thanks for your suggestion. I'm not actually worried about the speed of the algorithm. The user choice is by far the biggest bottleneck; that's why I'm trying to minimize the number of comparisons.
D. Pardal
CC BY-SA 4.0
2021-02-11T06:45:25.217Z
If you want to use it for user choices, you might want to use an *oblivious* sorting algorithm, so that the set of comparisons presented to the user does not depend on answer to the queries. Otherwise you would have to generate the queries dynamically based on the previously given answer, which I imagine is quite awkward from an UI point of view.
Emil Jeřábek
CC BY-SA 4.0
2021-02-11T07:20:38.797Z
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](https://en.wikipedia.org/wiki/Tournament_(graph_theory)), 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
CC BY-SA 4.0
2021-02-10T16:08:21.463Z
2021-02-10T16:08:21.463Z
user3209423940248
<p>I'm looking for a sorting algorithm that minimizes comparisons instead of time complexity.</p>
<p>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 <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span> such that <span class="math-container">$A&lt;B&lt;C$</span>, the algorithm shouldn't attempt to compare <span class="math-container">$A$</span> to <span class="math-container">$C$</span> if it already compared <span class="math-container">$A$</span> to <span class="math-container">$B$</span> and <span class="math-container">$B$</span> to <span class="math-container">$C$</span>. (Of course, if the algorithm compared <span class="math-container">$A$</span> to <span class="math-container">$B$</span> and then <span class="math-container">$A$</span> to <span class="math-container">$C$</span>, it would then also need to compare <span class="math-container">$B$</span> to <span class="math-container">$C$</span>. That's okay.)</p>
<p>Since sorting algorithms have been studied for decades, I'm guessing there already exists an algorithm for this.</p>
<p>My use case is allowing a user to sort things by preference by showing two of those things side-by-side.</p>

CC BY-SA 4.0
2021-02-10T16:31:46.003Z
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
<sorting>
A sorting algorithm that uses the minimum comparasions possible
D. Pardal
# A sorting algorithm that uses the minimum comparasions possible

(Asked by: username_0 on 2021-02-10)

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.

**Tags:** sorting

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2021-02-10. Score: 2 | Accepted answer

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.

That said, for practical purposes I suggest you use the sorting algorithm already implemented in your prefered programming language, as it is most likely been highly optimized, and would work faster than if you implement it yourself, unless you have a very specially structured input.

[1] <https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.79>

> **Comments:**
> **username_0**: Since asking the user is an asynchronous operation, using the built-in sorting algorithm in JavaScript is not possible. Binary insertion sort sounds like a good idea.  
> **username_2**: I'm not sure I follow, but if you wish to implement the sorting algorithm yourself, you might want to consider quicksort as (a) it is very fast in-practice (b) it is very easy to implement, and (c) it works very well with CPU caching (though I am not an expert in the subject of in-practice sorting algorithms)  
> **username_0**: Thanks for your suggestion. I'm not actually worried about the speed of the algorithm. The user choice is by far the biggest bottleneck; that's why I'm trying to minimize the number of comparisons.  
> **username_3**: If you want to use it for user choices, you might want to use an *oblivious* sorting algorithm, so that the set of comparisons presented to the user does not depend on answer to the queries. Otherwise you would have to generate the queries dynamically based on the previously given answer, which I imagine is quite awkward from an UI point of view.  
> **username_3**: 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](https://en.wikipedia.org/wiki/Tournament_(graph_theory)), so if you ask for $A<B$ and $B<C$ and infer $A<C$, the user will complain that they actually prefer $C<A$.  

---

