Additional notes
Sorting is the fundamental algorithmic problem in computer science, and it has a long history. KnuthD. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, second edition, 1997. attributes the merge-sort algorithm to von Neumann (1945). Quicksort is due to HoareC. A. R. Hoare. Algorithm 64: Quicksort. Communications of the ACM, 4(7):321, 1961.. The original heap-sort algorithm is due to WilliamsJ. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347–348, 1964., but the version presented here (in which the heap is constructed bottom-up in O(n) time) is due to FloydR. W. Floyd. Algorithm 245: Treesort 3. Communications of the ACM, 7(12):701, 1964.. Lower bounds for comparison-based sorting appear to be folklore. The following table summarizes the performance of these comparison-based algorithms: