The second segment all elements are greater or equal to the pivot value. Sort the two segments recursively. Quicksort is fastest on average, but sometimes unbalanced partitions can lead to very slow sorting. Mergesort Start from two sorted runs of length 1, merge into a single run of twice the length. Repeat until a single sorted run is left.
Performance is second place on average, with quite good speed on nearly sorted array.
Mergesort is stable in that two elements that are equally ranked in the array will not have their relative positions flipped. Heapsort Form a tree with parent of the tree being larger than its children. Remove the parent from the tree successively. On average, Heapsort is third place in speed. Heapsort does not need extra buffer, and performance is not sensitive to initial distributions.