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 开发者_Python百科SomeGuysLastName Theorem?

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.

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