An inefficient O (n 2) sorting algorithm that works by exchanging neighboring elements to propagate one element at a time to its correct position in the sorted set.
An O (n lg n) algorithm that requires three times the space of the data. It works by pairing up elements to promote a “winner” as the next element to be placed in the sorted set.
An efficient sorting algorithm that uses a heap (see Chapter 10) to build a sorted set. Heapsort runs in O (n lg n) and sorts in place. However, a good implementation of quicksort generally beats it by a small constant factor.
A sorting algorithm that behaves like quicksort, but detects when it would be better to switch to heapsort. By doing this, in some cases it gains a slight performance advantage over quicksort.
A linear-time sorting algorithm on average for data that is uniformly randomly distributed. It works by distributing the data into several buckets and sorting the buckets to produce a sorted set.