Let L be a list of n distinct elements. Any sorting algorithm that sorts L by comparison of the keys...

1. Let L be a list of n distinct elements. Any sorting algorithm that sorts L by comparison of the keys only, in its worst case, makes at least O(nlog2n) key comparisons.

2. Both the quick sort and merge sort algorithms sort a list by partitioning it.

3. To partition a list, the quick sort algorithm first selects an item from the list called pivot. The algorithm then rearranges the elements so that the elements in one of the sublists are less than pivot and the elements in the other sublist are greater than or equal to pivot.