CSC152 2006S, Class 49: Faster Sorts

Admin:
* Office hour signup outside office 
* Are there questions on Exam 3?
* In an attempt at supporting today's protest, I will only hold half a class today.

Overview:
* Divide-and-Conquer Sorting.
* Merge Sort.
* Iterative Merge Sort.
* Asymptotic Analysis of Merge Sort.
* Quicksort.

More Efficient Sorts

* Sort more efficiently by "divide and conquer"
* Two ways to divide:
  * First half vs. second half  "Merge sort"
  * Smaller vs. larger C.A.R. Hoare "Quicksort"

* Vector [23, 5, 1, 22, 0, 50, 18, 10]

* Divide into two halves
  * First half [23, 5, 1, 22]
  * Second half [0, 50, 18, 10]
* Sort the halves
  * F: [1,5,22,23]
  * S: [0,10,18,50]
* Put them back together (Merge)
  * Take the smaller first element of either half
    * Result: [0, ...]
  * Lop off that element
    * F: [1,5,22,23]
    * S: [10,18,50]
  * Do it again
    * Result: [0, 1, ....]
    * F: [5,22,23]
    * S: [10,18,50]
  * Do it again
    * Result: [0, 1, 5, ....]
    * F: [22,23]
    * S: [10,18,50]
  * ...
  * When you run out of stuff in one part, shove the other part at the end
* When we sort the halves, do it recursively
  * Base case: Empty: Sorted. // May not be necessary
  * Base case: One element: Sorted.

* Running time? [See figure]
  O(nlogn)
* Beats the O(n^2) for Friday's
* Equal to Heapsort
* Is this sorting algorithm stable?  Can we make it stable? 
  * Stable: Equal elements preserve order
  * If when we're merging, we take from the left half when confronted with equal elements, it's stable

You can do a more formal analysis in combinatorics, using recurrence relations

t(n) = n + 2*t(n/2)
t(n) = n + 2*(n/2 + 2*t(n/4))
t(n) = n + n + 4*t(n/4)
...

Other way to divide and conquer: By size (small and large)

* Vector [23, 5, 1, 22, 0, 50, 18, 10]
* Small:
  * Large for this list: 23, 22
  * Small for this list: 5, 1

* new list:
  * Large:
  * Small: -1, -1000
  * But what if the rest are all < -1000
* Need some context for determining large and small
  * Find largest O(n)
  * Find smallest O(n)
  * Average O(1)
  * Things smaller than average are small, things larger than average are larege
  * Try 1, 2, 4, 8, 16, 32, 4, 128, 256, 512
* Hoare's great idea: Guess the median, most of the time you're close
  * Chance is your friend
  * Empirical data support his claim

* Two key ideas in Quicksort
  * Divide-and-conquer
  * Chance is your friend

* Merging is easy in Quicksort: Concatenate
* Phrased as divde-and-conquer
  * Pick a pivot
  * Split into small and large
  * Sort two halves
  * Concatenate

Sam Rebelsky never logs out and [athanasa] doesn't have any lame ideas. Sad...