more sorting:  selection sort and mergesort
also, time permitting, implementing trees


____________________________________________________________
sorting

............................................................
selection sort 

overview and implementation (Slide V-43)

asymptotic time complexity
  worst case:  O(n^2)
  best case:  O(n^2) 

............................................................
mergesort

recall basic strategy for recursive sorting (V-18, V-19)  

algorithm review:  function merge at core (V-34)
  to sort subarray...
    split subarray in half
    recursively sort each subarray
    merge the subarray halves together

implementation review

running time analysis (V-39)

comparing with other algorithms (V-40)
  extra storage
  
............................................................
summary

sorts we've seen
  insertion sort
  quicksort
  selection sort
  mergesort 
    like quicksort, naturally recursive, O(n lg n) worst case

criteria
  running time:  worst, typical case
  cases w/ bad performance; bad cases specific to each algorithm
  code complexity