Lower bounds for sorting in Design and analysis of algorithms free pdf
Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size. Control, data movement, and all other aspects of the algorithm are ignored. Figure shows the decision tree corresponding to the insertion sort algorithm from operating on an input sequence of three elements.