Sorting Algorithm - Overview

Algorithm               Time  w (orst)                               Comments
                                          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

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