Merge Sort
> Click or hit ControlEnter to run the code above
Review: Recursive Tree Traversal
Let’s find all nodes in the tree and add them to a list.
What’s Our (Recursive) Algorithm?
Recursive Tree Traversal

Base case: We’ve reached a
null
node, at which point we can stop. 
Recursive step: Consider our right tree and left tree separately.

Combine results: Add ourselves to the list of nodes.
Java ArrayList
s
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 builtin implementations.
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
List list = new ArrayList();
List anotherList = new LinkedList();
> Click or hit ControlEnter to run the code above
> Click or hit ControlEnter to run Example.main above
There Are Many Sorting Algorithms
And we won’t discuss them all…

Insertion sort (today)

Selection sort (lab)

Merge sort (today)

Quicksort (Monday)

Bubble sort (lab)

And even new ones, like Timsort (circa 2002)
Insertion Sort: Overview
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
Insertion Sort: Overview
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
Insertion Sort: Insertion
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
Insertion Sort: A Single Step
3 
4 
5 
7 
8 
11 
6 
1 

Let’s look at one step in more detail
Insertion Sort: A Single Step






6 

3 
4 
5 
7 
8 
11 

1 

Let’s look at one step in more detail
Insertion Sort: A Single Step





6 


3 
4 
5 
7 
8 
11 

1 

Let’s look at one step in more detail
Insertion Sort: A Single Step





6 


3 
4 
5 
7 
8 

11 
1 

Let’s look at one step in more detail
Insertion Sort: A Single Step





6 


3 
4 
5 
7 

8 
11 
1 

Let’s look at one step in more detail
Insertion Sort: A Single Step




6 



3 
4 
5 
7 

8 
11 
1 

Let’s look at one step in more detail
Insertion Sort: A Single Step




6 



3 
4 
5 

7 
8 
11 
1 

Let’s look at one step in more detail
Insertion Sort: A Single Step



6 




3 
4 
5 

7 
8 
11 
1 

Let’s look at one step in more detail
Insertion Sort: A Single Step
3 
4 
5 
6 
7 
8 
11 
1 

Let’s look at one step in more detail
> Click or hit ControlEnter to run the code above
Insertion Sort Runtime
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)
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.
Java Generics (Brief Digression)
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 builtin implementations.
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
List list = new ArrayList();
List anotherList = new LinkedList();
> Click or hit ControlEnter to run Example.main above
Compiler Errors v. Runtime Errors
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.
Generics
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 ControlEnter to run Example.main above
We’ll Return to Generics
And talk about how to use them in your own classes. But that’s all for today.
Merge Runtime
Time complexity:

Worst case: O(n)

Best case: O(n)

Average case: O(n)
CS 125 Project Fair
Fair Overview
This will be our fourth CS 125 Final Project Fair: bigger and better than ever.

Date: Thursday 12/12/2019, time TBD.

Participation: Optional but worth 1% extra credit

Location: TBD, but probably in and around Siebel.
How to Not Get a Great CS Job
All of you will get a job. Not all of you will get a great 1 job.
Here’s a good strategy for not getting a good job:

Take CS classes.

Do the projects.

Get good grades.

Don’t do any side projects: focus on grades instead.
How to Get a Great CS Job
Show your passion for technology.

The CS 125 Project Fair is intended to get you started doing that.
Example Spring 2019 Fair Projects
Announcements

Have a great weekend!