Talk:Comparison sort

Proof of lower bound

I'd like to request a more intuitive explanation of the O(nlog(n)) bound, if possible. It seems like it should be a fairly simple concept to illustrate, but the current text is not all that easy to follow. ~ Booyabazooka 05:11, 6 April 2006 (UTC)

I would go even further and question the lower bound statement as Insertion Sort runs in O(n) for best case. maju (talk) 14:17, 13 April 2013 (UTC)

The lower bound is a bound on the worst case time. I can edit to explain this better. Dcoetzee 17:08, 10 June 2013 (UTC)

Properties of the < operator

Last month someone changed "less than" to "less than or equal" in the articles's first paragraph. This was obviously done to make it agree with the subsequent three conditions, which are expressed in terms of $\leq$. But comparison sorts are usually expressed in terms of <, in my experience.

Worse, looking at the three conditions, I realize that they aren't actually correct. Every comparison sort I've come across expects a total order on equivalence classes, which isn't the same thing as a total order. So what are the correct conditions on the < operator? Based on the conditions for total orders and equivalence classes, I came up with this set, which I think is sufficient:

• $a\not <a$
• $a<b\ \wedge \ b<c\ \Rightarrow \ a<c$
• $a=b\ \wedge \ b=c\ \Rightarrow \ a=c\quad {\mbox{where}}\quad x=y\ \equiv \ x\not <y\ \wedge \ y\not <x$

But I'd rather have an official set of axioms from a reputable source. Anybody know where to find one? -- BenRG 23:48, 8 October 2006 (UTC)

My experience is that formal theory about these things is invariably expressed in terms of a $\leq$-like relation, in which case what you're talking about is a preorder with a totality condition. Given that the order is total, writing < would not be essentially different; it is just a matter of swapping left for right and then negating the relation. The practical implementations of sorting routines (and other generic comparison-based algorithms) I have met predominantly use neither style, but expects the comparison function to do a three-way split, returning one of < or = or > for any pair of elements. Henning Makholm 19:56, 15 October 2006 (UTC)

I think this article needs a word on adaptive comparison sort. http://en.wikipedia.org/wiki/Adaptive_sort

Clarification for section on Lower bound for the average number of comparisons

For example, for n = 3, the lower bound for the worst case is 3, the lower bound for the average case as shown above is approximately 2.58, while the highest lower bound for the average case is 8/3, approximately 2.67.

So 2.58 ≈ log₂(n!) for n = 3, but the figure of 8/3 ≈ 2.67 has given me a bit of pause. I think I may sort of see what the argument is. Seems like the idea is to find the first rational value of x which is clearly meeting the requirement 2^x ≥ 6, but which is less than 3 (since x = 3 clearly meets the requirement). So if one iterates like: 1/1, 2/2, 2/1, 3/3, 3/2, 3/1, 4/4, 4/3, etc. 8/3 is the first one that meets the requirement (as the cube root of 256 is more than 6, 6³ being 216). Maybe some clarification could be helpful, or maybe that could be deleted and the sentence could just end with the value 2.58. Jjjjjjjjjj (talk) 06:26, 3 August 2017 (UTC)

I have clarified the difference between information-theoretic lower bound and the lower bound of average case derived from Decision tree model. The formula explains. Anonymous, 05:35, 12th 2020 (UTC+8). — Preceding unsigned comment added by 124.9.193.131 (talk) 21:37, 11 February 2020 (UTC)