CSC152 2005S, Class 52: Exam 3 Distributed

Admin:
* Exam 3 distributed
  * Not all code ready.  Expect it this afternoon.
* Don't forget the picnic today!   5 p.m.  Merrill Park.  
  (Approximately main and 12th)
* Monday is *not* discussion of Exam 3
* Elizabeth recommends that you play with
  http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Overview:
* Questions on Merge sort and more
* About the exam
* Lab

Why does the merge step take O(n) steps?
* It takes O(1) step to move a value into the "merged array"
* There are n values in the "merged array"

Can we review merge?
[ 1 3 5 6 7 9 9 ] [ 2 2 2 4 8 ] => [  ]
  *                 *
[ 1 3 5 6 7 9 9 ] [ 2 2 2 4 8 ] => [ 1  ]
    *               *
[ 1 3 5 6 7 9 9 ] [ 2 2 2 4 8 ] => [ 1 2 ]
    *                 *
[ 1 3 5 6 7 9 9 ] [ 2 2 2 4 8 ] => [ 1 2 2 ]
    *                   *
[ 1 3 5 6 7 9 9 ] [ 2 2 2 4 8 ] => [ 1 2 2 2 ]
    *                     *
[ 1 3 5 6 7 9 9 ] [ 2 2 2 4 8 ] => [ 1 2 2 2 3 ]
      *                   *

Why do some implementations of mergesort use "middle"
* If it's "in place", the middle serves the same purpose as it does with binary search

/On to the exam/