Held: Friday, 6 May 2016

Back to Outline 51 - Insertion Sort. On to Outline 53 - Project Assessment: Images.

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)

Overview

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

Administrivia

• Continue partners.
• Penultimate Friday PSA.
• I will continue to bring you food (or food-like substances) until I am caught up on grading.
  
  • Today: Cheetos and Donuts (coherency is not my strong suit)
• Sunday is Mother's day. If you are fortunate enough to have a mother or mother equivalent who is important to you, make sure to let that person know.
• A second section of CSC 161 has been added at 10 a.m. It even has a few open slots.

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • Ask me about other available times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Review Sessions
  • Wednesday at 8pm in CS commons with ???
  • Thursday at 10 am with SamR
  • Thursday at 8pm in CS commons with ???

Upcoming Work:

• No more readings!
• Lab Writeup:
  • Send email titled CSC 151 Lab Writeup 52 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Tuesday.
  • THE LAST WRITEUP!
• Exam 4 due next Tuesday
  • Prologue due Friday night
  • Epilogue due next Tuesday.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Finals week's Inside Grinnell. Tuesday, May 17 at noon in JRC 101. Food served.

Peer

• Rushdie's East/West, May 6/7 at 7:30 p.m. No tickets necessary.
• Humans of Grinnell College on Facebook.
• KGY: Koreagraphy presents K-POP Gardner. Friday at 10:00 p.m.

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203.
  Just show up; you don't need to sign up.
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

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.