Held: Friday, 5 December 2014

Back to Outline 51 - Project Assessment: Algorithms. On to Outline 53 - Objects 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
• EBoard 52 (Source 52) (HTML 52)

Overview

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

Administrivia

• Continue partners!

Upcoming Work

• Exam 4 due MONDAY, December 8.
  • Prologue due TONIGHT
• Reading for Monday: Objects in Scheme
• No lab write-up for today. (I think we're done with lab write-ups for the semester.)

Extra Credit Opportunities

Academic

• Inside Grinnell Thursday the 11th at noon in JRC 101: Grinnell's Endowment: What Can and Can't it Do?

Peer Support

• Karan's radio show 11pm Thursday nights on KDIC
• Evan's radio show 5pm Friday nights on KDIC
• Donna's radio show Sunday midnight on KDIC
• Noteworthy at the Dance performance (Once Upon a Time, Splintered), December 4 and 5 in Flanagan
• One acts, December 6 and 7 in Roberts
• Pioneer Swim Meet, December 5 and 6 in the Osgood

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.