Merge Sort

Merge Sort
> Click or hit Control-Enter to run the code above

And we won’t discuss them all…

Insertion sort (Wednesday)
Selection sort (lab)
Merge sort (today)
Heapsort
Quicksort (today)
Bubble sort (lab)
And even new ones, like Timsort (circa 2002)

Measure	Best Case	Worst Case	Average Case
Time	O(n)	O(n^2)	O(n^2)
Space	O(1)	O(1)	O(1)

Measure

Best Case

Worst Case

Average Case

Time

O(n)

O(n^2)

Space

O(1)

Optimal sorting algorithms should be O(n log n) in the worst case and close to O(n) in the best case.

1	8	9	12
2	5	7	10

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

1	8	9	12
2	5	7	10

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

	8	9	12
	2	5	7	10
1

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

	8	9	12
	2	5	7	10
1

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

		8	9	12
		5	7	10
1	2

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

		8	9	12
		5	7	10
1	2

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

			8	9	12
			7	10
1	2	5

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

			8	9	12
			7	10
1	2	5

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				8	9	12
				10
1	2	5	7

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				8	9	12
				10
1	2	5	7

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				9	12
				10
1	2	5	7	8

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				9	12
				10
1	2	5	7	8

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				12
				10
1	2	5	7	8	9

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				12
				10
1	2	5	7	8	9

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				12

1	2	5	7	8	9	10

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

				12

1	2	5	7	8	9	10

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays



1	2	5	7	8	9	10	12

Merge sort harnesses the fact that it is easy to merge two already-sorted arrays

> Click or hit Control-Enter to run the code above

Time complexity:

Worst case: O(n)
Best case: O(n)
Average case: O(n)

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

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.

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 Control-Enter to run the code above

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).

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

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)

Measure

Best Case

Worst Case

Average Case

Time

O(n log n)

Space

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 is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

8	5	7	3	4	11	6	-1

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

8	5	7	3	4	11	6	-1

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

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

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

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

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

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

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

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

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.)

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.

There Are Many Sorting Algorithms

Insertion Sort Runtime

We Can Do Better

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Sort: Overview

Merge Runtime

But What About Mergesort?

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

What’s Our (Recursive) Sorting Algorithm?

Recursive Mergesort

Merge Sort Runtime

Merge Sort Runtime

Merge Sort Runtime

Divide and Conquer

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

CBTF Programming Problems

Announcements