Held: Monday, 28 April 2014

Back to Outline 48 - Insertion Sort. On to Outline 50 - 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 49 (Source 49) (HTML 49) (PDF 49)

Overview

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

Administrivia

• Remember! You have a responsibility to cite all of the resources you use, even if you don't copy and paste.

Upcoming Work

• Optional assignment for tonight: Exam 3 prologue.
• Reading for Monday: Merge Sort.
• Homework for Thursday: Exam 3.
• Lab writeup: Exercise 6 and Extra 1

Extra Credit

• CS Extra Thursday: Edward Snowden TED Talk
• CS Table Friday: Edward Snowden

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.