CMU 15-110: Principles of Computing
Searching and Sorting

1. Simulations
   
   • Searching
     See here for linear search and binary search.
   
   
   • Sorting
     See here for selection sort and merge sort.


2. What You Need To Know
   
   1. How linear search works: check each item in order.
   2. How binary search works: for a sorted list, keep checking the middle item and eliminating half the remaining items on each check.
   3. What Big-Oh is. Basically, ignore constants and lower-order terms.
   4. Linear search through a list with n values is O(n).
   5. Binary search through a sorted list with n values is O(logn).
   6. logn is much, much smaller than n
   7. So binary search is much, much faster than linear search.
   
   
   8. When we say logn without a base, we mean base 2.
   9. 2¹⁰ is about 1 thousand, 2²⁰ is about 1 million, 2³⁰ is about 1 billion.
   10. log(1 thousand) is about 10, log(1 million) is about 20, log(1 billion) is about 30.
   
   
   11. How selection sort works: keep selecting the largest remaining element and swapping it into place.
   12. How merge sort works: keep merging sorted sub-lists of size k into sorted sub-lists of size 2k (so, 1 into 2, then 2 into 4, and so on).
   13. Selection sort is O(n²). Prove this.
       • The first pass of selection sort takes n steps (n-1 compares and one swap).
       • The second pass takes (n-1) steps.
       • And so on.
       • So: total steps = n + (n-1) + ... + 2 + 1 = (n/2)(n+1)
       • So: total steps is O(n²).
   14. Merge sort is O(nlogn). Prove this.
       • The first pass takes 3n steps -- n compares, n copies down, n copies back up.
       • In fact, each pass takes 3n steps.
       • So the total steps is 3n * (# of passes).
       • There are logn number of passes (since the size of the sorted sublists doubles on each pass).
       • So the total steps is 3n * (logn).
       • So the total steps is O(nlogn).
   15. Since logn is much smaller than n, nlogn is much smaller than n².
   16. So merge sort is much, much, much faster than selection sort.