Held: Wednesday, 15 October 2014

Back to Outline 27 - Quadratic Sorts. On to Outline 29 - Quicksort.

Summary

We consider the merge sort algorithm, our first O(nlogn) sorting algorithm.

Related Pages

• Reading: Merge sort
• Lab: Merge sort
• EBoard 28 (Source 28) (HTML 28)

Overview

• Lower bounds on sorting.
• Divide and conquer algorithms.
• An introduction to merge sort.
• Analyzing merge sort.

Administrivia

• New lab partners (keep for the rest of this week)
• Office hours
  • Normal this week (Th 1:45-3:15; walking 1:15-1:45); No hours Friday
  • I no longer know where I am in the morning. Email me to figure it out.
• Review session Thursday at 11am.
• Note: Some of you are good about asking me for help in person. Some of you are good about asking me for help via email. Some do neither.
  Students from the past two semesters of CSC 207 keep saying "Once I realized that Sam was actually helpful, I started asking for help." So, I'm going to leave the room for five minutes and let you talk to each other about asking me for help. (You can also make a list of things that I can do better, other than magically finding time for more office hours.)

Upcoming Work

• Exam 1 due Thursday.
  • Required epilogue due Friday night (or before).
• Reading for Friday:
  • Quicksort

Interesting Things to Do

• I'm told that there is a cool concert tonight.

Extra Credit

Academic

• Thursday Extras, 4:30 p.m. Thursday, October 16, Grad School in CS
• CS Table Friday (Day PDR): Debrief on GHC

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music
• Ezra's Radio show Thursdays at midnight. Radio melodrama.

An introduction to merge sort

• There's a theoretical analysis that shows that O(nlogn) comparisons are necessary for a comparison-based sort.
• All of the sorting algorithms we've seen so far are O(n^2).
• Can we do better? (Can we achieve the known lower bound?)
• One strategy for writing faster algorithms is "divide and conquer". When presented with a large problem,
  • split it into two parts
  • solve each part
  • combine the solutions
• The easiest way to split an array: first half and second half.
• We sort the two halves.
• What can we do after sorting the two halves?

Analysis

• Let's let t(n) represent the time mergesort takes on input of size n.
• To sort an array of size n, we must sort two arrays of size n/2, and then merge the two. Merging takes n steps.
• We have a simple recurrence relation: t(n) = 2*t(n/2) + n
• We can explore recurrence relations top-down or bottom up.
• Bottom up
  • t(1) = 1
  • t(2) = 21 + 2 = 4
  • t(4) = 24 + 4 = 12
  • t(8) = 212 + 8 = 32
  • t(16) = 232 + 16 = 80
  • Hmmm ...
• Top down
  • t(n) = 2t(n/2) + n
  • t(n) = 2(2t(n/4) + n/2) + n // Expand t(n/2)
  • t(n) = 22t(n/4) + 2n/2 + n // Distribute
  • t(n) = 4t(n/4) + 2n // Simplify
  • t(n) = 4(2t(n/8) + n/4) + 2n // Expand t(n/4)
  • t(n) = 42t(n/8) + 4n/4 + 2n // Distribute
  • t(n) = 8t(n/8) + 3n // Simplify
  • t(n) = 8(2t(n/16) + n/8) + 3n // Expand t(n/8)
  • t(n) = 82t(n/16) + 8n/8 + 3n // Distribute
  • t(n) = 16*t(n/16) + 4n // Distribute
• I see a pattern:
  • t(n) = 2^k*t(n/(2^k)) + kn
• If we let 2^x = n, we get
  • t(n) = n*t(1) + xn
  • If 2^x = n, then x = log2(n)
  • So t(n) = n + log2(n) * n
• The second term dominates. t(n) is in O(nlogn)

Lab

• If you haven't already done so, fork and clone the code from https://github.com/Grinnell-CSC207/sorting
• Write a loop invariant for Utils.merge.
• Implement Utils.merge.
• Extra problems to gather data and/or do bottom-up merge sort.