Sorting Algorithms that run in O(n log n) time
  
  Insertion Sort (Chap 13-14 CRL; Chap 4.4-4.5 AHU; Chap 12-13 Kozen).
    using binary search and search trees.

  Repeatly (recursively) find the largest element 
    (Chap 7 CLR; Chap 3.4 AHU; Kozen 8-9 Kozen).
    using a heap (Heapsort)

  Divide and Conquer 

   1) Mergesort (Doing the work after the recursive calls)
       (Chap 2.6 AHU; Chap 1.3 CLR)

   2) Marriage-before-conquest 

      a) Deterministic: Recursively using a fast median algorithm 
            (Chap 3.6 AHU; Chap 10 CLR). 

      b) Randomized: Quicksort (Chap 8 CLR; Chap 3.5 AHU).


Non-comparison based sorting algorithms.

  Bucket Sort (9.4 CLR).

  Radix Sort (Chap 3.2 AHU; 9.3 CLR).
   

Computing the median value and selecting the k-th largest element in
   O(n) time. 

 Multilevel Algorithms 

  Deterministic: (Chap 3.6 AHU; Chap 10.3 CLR)

  Randomized: Quickselect (Chap 3.7 AHU; Chap 10.2 CLR)