CMU 15-112: Fundamentals of Programming and Computer Science
Class Notes: Searching

1. Sorting
   1. Sorting Links
      
      • Wikipedia page on Sorting
      • David Eck's xSortLab applet (or you might try this jar file )
      • Excellent sorting animation website
      • Sorting algorithm animation video (15 algorithms in 6 minutes)
      • Even more sorting algorithm animations
   
   
   2. SelectionSort vs MergeSort
      • Definitions
        • Selection Sort: repeatedly select largest remaining element and swap it into sorted position
        • Mergesort: sort blocks of 1's into 2's, 2's into 4's, etc, on each pass merging sorted blocks into sorted larger blocks
      • Analysis
        This is mostly informal, and all you need to know for a 112-level analysis of these algorithms. You can easily find much more detailed and rigorous proofs on the web.
        • selectionsort
          On the first pass, we need N compares and swaps (N-1 compares and 1 swap).
          On the second pass, we need only N-1 (since one value is already sorted).
          On the third pass, only N-2.
          So, total steps are about 1 + 2 + ... + (N-1) + N = N(N+1)/2 = O(N²).
        
        
        • mergesort
          On each pass, we need about 3N compares and copies (N compares, N copies down, N copies back).
          So total cost = (3N steps per pass) x (# of passes)
          After pass 0, we have sorted lists of size 2⁰ (1)
          After pass 1, we have sorted lists of size 2¹ (2)
          After pass 2, we have sorted lists of size 2² (4)
          After pass k, we have sorted lists of size 2^k
          So we need k passes, where N = 2^k
          So # of passes = k = log₂N
          Recall that total cost = (3N steps per pass) x (# of passes)
          So total cost = (3N)(log₂N) = O(NlogN).
          Note: This is the theoretical best-possible Big-O for comparison-based sorting!