Merge Sort

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

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

Good luck on today’s quiz! And stay warm tonight…

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

Announcements