Talk:Comparison sort

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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 \le. 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)
Retrieved from "http://en.wikipedia.org../../../c/o/m/Talk%7EComparison_sort_d048.html"