We started from discussing how people make money by selling stocks.
People sell stocks a few seconds before the peak to get the largest benefit.

Then we move on to discuss the sorting problem.

Sorting Problem:

If you have a bunch of numbers:
unsorted: 5, 10, 7, 8, 2, 3, 5, 6
After sorted: 2, 3, 5, 5, 6, 7, 8, 10

computers spend lots o energy and time on sorting, so this is well studied. Here are some methods for sorting.
Eg1. Q: How big an array of stuff can you sort in a given time?
              How to do it efficiently (or with computer)?
              Here we have a long list of numbers that haven't been sorted. The challenge is how to sort it without using computer.
If you have 3000 numbers to sort. All those numbers are integers between 1 and 100.
         A: Sort 1-9 in a file. Sort 10-19 in one file….
This is the Bucket Sort. However, Bucket Sort isn't always the best way. Bucket Sort is used when there are lots of data but small range.

Eg2. Q: Sort 3000 names.
         A: Sort alphabetically.

Eg3. A fast way is to divide the whole list into two sets, sort each and merge the result
5 10 7 8 | 2 3 5 6
C---5               2---A
       7               3---B
       8               5---C
      10              6---D
when we have a set of numbers, we randomly divide them evenly into two sets and then sort each set. For example:
10 7 | 8 2
   7        2
   10      8
Merging is done by comparing the smallest elements, then outputting the smallest, then compare the next pair and so on.
Here is an example [Tiffany, give an example]

Thus, the total time would be:
Time(n)=2*Time(n/2)+n
If there are only two elements in the set, time for sorting is:
Time(2)=1
This is the Merge Sort.

How to get the time for sorting a single set?
We used the approach of guessing and then prove our guessing is correct in the end.
If Time(k)=klog2k
If the equation above is true,
Time(2k)=2*Time(k)+2k
                =2klog2k+2k
                =2k(log2k+1)
                =2k(log2k+log22)
                =2klog22k
Guessing is correct.
The Recurrence Equation is satisfied.

Additional notes for Merge Sorting:
1. You can do Merge Sorting in parallel.
2. Quick Sort costs the same time, but only in “expected time” (intuitively, this means “usually”)

Mergesort(array A)
split(A) into two pieces, Afirst and Asecond.
then merge(mergesort(Afirst), mergesort(Asecond))
If A is small enough
	sort(A) &
         return
Main points here are:
A. Different methods will cost different time.
B. It can be easily parallelized.
C. Recursion Idea is not effective for fibonacci but is efficient for sorting problem.

Homework:
Coach’s Puzzle
Mastermind