Insertion and Merge Sort

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

Keep up the good work!

And we won’t discuss them all…

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

8

5

7

3

4

11

6

-1

Insertion sort divides the array into two parts: a sorted part and an unsorted part
The sorted part starts at the beginning of the array and grows during each step

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

Insertion sort divides the array into two parts: a sorted part and an unsorted part
The sorted part starts at the beginning of the array and grows during each step

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

In each step we take the first item from the unsorted region and insert it in the right place in the sorted region

3	4	5	7	8	11	6	-1

3

4

5

7

8

11

6

-1

Let’s look at one step in more detail

						6
3	4	5	7	8	11		-1

Let’s look at one step in more detail

					6
3	4	5	7	8	11		-1

Let’s look at one step in more detail

					6
3	4	5	7	8		11	-1

Let’s look at one step in more detail

					6
3	4	5	7		8	11	-1

Let’s look at one step in more detail

				6
3	4	5	7		8	11	-1

Let’s look at one step in more detail

				6
3	4	5		7	8	11	-1

Let’s look at one step in more detail

			6
3	4	5		7	8	11	-1

Let’s look at one step in more detail

3	4	5	6	7	8	11	-1

3

4

5

6

7

8

11

-1

Let’s look at one step in more detail

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

Time complexity:

Worst case: O(n^2) if the array is sorted in descending order (for this implementation)
Best case: O(n) if the array is already sorted (for this implementation)
Average case: O(n^2)

Space complexity: can be done in place with one temporary variable, so O(1)

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.

Lists are one of the two data structures you meet in heaven.

We’ve studied them in class together. But you’ll usually use Java`s built-in implementations.

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

List list = new ArrayList();
List anotherList = new LinkedList();

> Click or hit Control-Enter to run Example.main above

Java and many languages that followed it have tried to transform runtime errors into compiler errors. Why?

You compile your code before it runs: and so before you have to demo it to a client, or before you deploy it to hundreds of users.
Catching errors at this stage is critical.

Java generics allow us to create reusable classes while allowing the compiler to check our code for correctness.

import java.util.List;
import java.util.ArrayList;

List<Integer> integerlist = new ArrayList<Integer>(); // This is list of Integers
List<String> stringList = new ArrayList<String>(); // This is a list of Strings

> Click or hit Control-Enter to run Example.main above

And talk about how to use them in your own classes. But that’s all for today.

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.

MP4 is out. Please get started!
I have office hours today from 1–3PM in Siebel 2227. Please come by and say hi!

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

You’re Doing Great

There Are Many Sorting Algorithms

Insertion Sort: Overview

Insertion Sort: Overview

Insertion Sort: Insertion

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort: A Single Step

Insertion Sort Runtime

Insertion Sort Runtime

We Can Do Better

Java Generics (Brief Digression)

Compiler Errors v. Runtime Errors

Generics

We’ll Return to Generics

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

Announcements

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11

8	5	7	3	4	11	6	-1
8	5	7	3	4	11	6	-1
5	8	7	3	4	11	6	-1
5	7	8	3	4	11	6	-1
3	5	7	8	4	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	7	8	11	6	-1
3	4	5	6	7	8	11	-1
-1	3	4	5	6	7	8	11