Held: Wednesday, 29 April 2015

Back to Outline 49 - Insertion Sort. On to Outline 51 - Files in Scheme.

Summary

We continue our exploration of sorting by considering the applicability of divide-and-conquer to the problem of sorting. We look at one particular divide-and-conquer algorithm, merge sort. We explore how the running time for that algorithm varies based on the number of values we are sorting.

Related Pages

• Reading: Merge Sort
• Lab: Merge Sort
• Morning EBoard 50 (Source a.m. 50)
• Afternoon EBoard 50 (Source p.m. 50)

Overview

• More efficient sorting techniques.
• Divide and conquer, revisited.
• Merge sort.
• Analyzing merge sort.

Administrivia

• New partners! (for the last time)
• Don't forget to grab a yellow card.
• Review sessions Thursday at 1:15pm and 8pm.
• Friday is our last day of new material.

Upcoming Work

• Quiz Friday: Binary search, Sorting. Our last quiz.
• Exam 4 prologue due Friday night!
• Exam 4 due in electronic form on Monday night. Our last exam.
• Exam 4 epilogue due Monday night.
• Lab Writeup: 4fgh. Our last lab writeup. http://bit.ly/151-2015S-lab50
• Reading for Friday (final reading): Files in Scheme

Extra Credit Opportunities

Academic

• PBK Convo, Wednesday (TODAY).
• CS Extras Thursday, Brooks Davis on Unix stuff
• CS Table Friday, Last CS Table of the Year: Planning for next year

Peer Support (Morning Section)

• KY's radio show, "We Think We're Funny", 9-10pm Mondays
• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.
• Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

Peer Support (Afternoon Section)

• Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.
• Triathalon on Saturday
  • Participate!
  • Cheer! is acceptable too
• Quinceañera Saturday at some time in some place

Miscellaneous

• Donate to support Nepal. (List of agencies available via NYTimes)
  • Or put money in boxes labeled appropriately.
  • Fogfast - SGA is tabeling tonight or email to [services] with a subject of "Donate a Meal"

Other Good Things (no extra credit)

Key Ideas of Merge Sort

• Divide and conquer is often a useful design strategy.
• For sorting, natural division is "first half" / "second half".
• What do we do after sorting the two halves? Merge 'em.

An Alternate Implementation

• We can do something very much like merge sort while avoiding the splitting step.
• We start with a list of sorted lists, and repeatedly merge neighboring pairs.
• This technique is slightly easier to implement.
• This technique is much easier to analyze.

The Costs of Merge Sort

• What's the running time? We do approximately Nlog₂N* comparisons.
• The analysis:
  • N steps to merge 2 sorted lists of length N/2
  • N steps to merge 4 sorted lists of length N/4 into those two sorted lists.
  • N steps to merge 8 sorted lists of length N/8 into those four sorted lists.
  • And so on and so forth.
• Can we do better? Not if our sorting is based on comparing values to each other.

Lab

• Do the lab
• Pause to reflect.