CODEWITHSUNDEEP
algorithmsorting
Aaron Fi
Aaron Fi

Reputation: 10426

Who first proved that all comparison-based sorting is Omega(n lg n)?

Who first proved that all comparison-based sorting is at least Omega(n lg n)? Is there a name attached to this lower-bound? e.g. The SomeGuysLastName Theorem?

Upvotes: 1

Views: 313

Answers (2)

matt
matt

Reputation: 79803

My copy of 'Introduction to Algorithms' has this to say in the chapter notes for chapter 8, which is where this bound is discussed:

The decision-tree model for studying comparision sorts was introduced by Ford and Johnson (1). Knuth's comprehensive treatise on sorting (2) covers many variations of the sorting problem, including the information-theoretic lower bound on the complexity of sorting given here.

(1) Lester R. Ford, Jr. and Selmer M. Johnson. A tournament problem. The American Mathematical Monthly, 66:387-389, 1959.

(2) Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973.

Not a defininite answer to your question, but it's something.

Upvotes: 2

Harmen
Harmen

Reputation: 22446

Merge sort ( worst case scenario: n log n ) was invented by John von Neumann in 1945, so I think he was the first one to prove it.

But maybe a Greek proved it in 400BC, does it really matter?

http://en.wikipedia.org/wiki/Merge_sort

Upvotes: 1

Related Questions