Merge Sort
> Click or hit ControlEnter to run the code above
There Are Many Sorting Algorithms
And we won’t discuss them all…

Insertion sort (Wednesday)

Selection sort (lab)

Merge sort (today)

Quicksort (today)

Bubble sort (lab)

And even new ones, like Timsort (circa 2002)
Insertion Sort Runtime
Measure  Best Case  Worst Case  Average Case 

Time 
O(n) 
O(n^2) 
O(n^2) 
Space 
O(1) 
O(1) 
O(1) 
We Can Do Better
Optimal sorting algorithms should be O(n log n) in the worst case and close to O(n) in the best case.
Merge Sort: Overview




1 
8 
9 
12 




2 
5 
7 
10 









Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




1 
8 
9 
12 




2 
5 
7 
10 









Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





2 
5 
7 
10 
1 








Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





2 
5 
7 
10 
1 








Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





5 
7 
10 

1 
2 







Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





5 
7 
10 

1 
2 







Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





7 
10 


1 
2 
5 






Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





7 
10 


1 
2 
5 






Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





10 



1 
2 
5 
7 





Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





10 



1 
2 
5 
7 





Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




9 
12 






10 



1 
2 
5 
7 
8 




Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




9 
12 






10 



1 
2 
5 
7 
8 




Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 







10 



1 
2 
5 
7 
8 
9 



Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 







10 



1 
2 
5 
7 
8 
9 



Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 











1 
2 
5 
7 
8 
9 
10 


Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 











1 
2 
5 
7 
8 
9 
10 


Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview
















1 
2 
5 
7 
8 
9 
10 
12 

Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
> Click or hit ControlEnter to run the code above
Merge Runtime
Time complexity:

Worst case: O(n)

Best case: O(n)

Average case: O(n)
But What About Mergesort?
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
1 
10 
5 
6 
4 
11 
7 
1 
Each contiguous subarray of an array is, itself, an array.
Array Recursion
Just like with trees and lists, we need a way to both make the problem smaller and identify the smallest subproblem.

How do we make the problem smaller? Break the list into two smaller subarrays.

What’s the smallest subproblem? An array with a single item.
What’s Our (Recursive) Sorting Algorithm?
Recursive Mergesort

Base case: We’ve reached an array with just one value, so return in.

Recursive step: Split the array into two roughly equal parts.

Combine results: Merge the two smaller subarrays.
> Click or hit ControlEnter to run the code above
Merge Sort Runtime
Let’s consider an array of size 8:

Merge 1:

8 arrays of size 1 into 4 arrays of size 2

so 4 O(n) merges where n = 2


Merge 2:

4 arrays of size 2 into 2 arrays of size 4

so 2 O(n) merges where n = 4


Merge 3:

2 arrays of size 4 into 1 arrays of size 8

so 1 O(n) merges where n = 8


So given n = 8, we have done 3 O(n) steps, or O(n log n).
Merge Sort Runtime
Step 
















0 
8 

5 

7 

3 

4 

11 

6 

1 

1 

5 
8 


3 
7 


4 
11 


1 
6 

2 


3 
5 
7 
8 




1 
4 
6 
11 


3 




1 
3 
4 
5 
6 
7 
8 
11 




Merge Sort Runtime
Measure  Best Case  Worst Case  Average Case 

Time 
O(n log n) 
O(n log n) 
O(n log n) 
Space 
O(n) 
O(n) 
O(n) 
(Our implementation used a lot of extra space, but you can get by with just one extra array of size n.)
Divide and Conquer
Divide and conquer is an algorithm design paradigm based on multibranched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more subproblems of the same or related type, until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.
Quicksort: Overview
8 
5 
7 
3 
4 
11 
6 
1 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
8 
5 
7 
3 
4 
11 
6 
1 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 
5 
7 
3 
4 
6 
1 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 
3 
4 
1 
5 
7 
6 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 
3 
4 
1 
5 
7 
6 
8 
11 
3 
4 
1 
5 
7 
6 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 
3 
4 
1 
5 
7 
6 
8 
11 
1 
3 
4 
5 
6 
7 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 
3 
4 
1 
5 
7 
6 
8 
11 
1 
3 
4 
5 
6 
7 
8 
11 
1 
3 
4 
5 
6 
7 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
Quicksort: Overview
5 
7 
3 
4 
6 
1 
8 
11 
3 
4 
1 
5 
7 
6 
8 
11 
1 
3 
4 
5 
6 
7 
8 
11 
1 
3 
4 
5 
6 
7 
8 
11 
1 
3 
4 
5 
6 
7 
8 
11 

In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

This continues until arrays of size 1 are reached, at which point the entire array is sorted
CBTF Programming Problems
To prepare you for the final exam, On today’s quiz we have started using programming problems.
A few suggestions:

Budget your time carefully. If you start with the programming exercises, you may not leave enough time for the easier questions. If you leave the programming exercises to the end, you may run out of time.

You can submit as many times as you want—well, technically up to 100 times—but…

Grading is slow. Keep this in mind. (Sorry: not entirely our fault.)
Announcements

MP5 is due next Monday at 5PM.

Get your Android environment set up! Come to office hours if you need help.

We’ve added an anonymous feedback form to the course website. Use it to give us feedback!

My office hours continue today at 11AM in the lounge outside of Siebel 0226.