Sorting Algorithm - Overview

---

Algorithm               Time  w (orst)                               Comments
                                          a (verage)

---

                        Comparison Sorting Algorithms:  W(n lg n)

---

   Insertion                      w: Q(n²) 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(n²)                             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) 

---