This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing: Software / CompSci Mid‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing Mid This article has been rated as Mid-importance on the project's importance scale. This article is supported by WikiProject Software (assessed as Mid-importance). This article is supported by WikiProject Computer science (assessed as High-importance). Things you can help WikiProject Computer science with: edit history watch purge Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Computer science High‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science High This article has been rated as High-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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

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

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

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 ${\displaystyle \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:

• ${\displaystyle a\not <a}$
• ${\displaystyle a<b\ \wedge \ b<c\ \Rightarrow \ a<c}$
• ${\displaystyle 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)Reply

My experience is that formal theory about these things is invariably expressed in terms of a ${\displaystyle \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)Reply

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

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

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