Sorting Algorithm - Overview

a (verage)

Comparison Sorting AlgorithmsW(n lg n)

Insertion                      w: Q(n2)                                in place, stable
tight code, small constants,
outperforms Merge Sort for small n

Merge Sort                   w: Q(n lg n)                        not  in place, optimal

Heap Sort                     w: Q(n lg n)                        in place, optimal

Quick Sort                    w:  Q(n2)                             in place
tight code, small constants,
a:  Q(n lg n)                          outperforms Heap Sort in practice

Sorting in Linear Time (worst case or average)

Counting Sort                 w: O(n + k)                     Assume: all keys are in the range {1, 2,, ..., k}
stable, not in place

Radix Sort                      w: O(d (n + k ))                 Assume: all keys are in the range {1, 2,, ..., k}
and  are represented by  d digits
stable

Bucket Sort                    a: O(n)                               Assume: all keys are in the range  [ 0, 1)