Today’s Musical Selections
Today’s great song is from Haerts.
Quicksort
Review: 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).
Review: 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 




Review: 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
Quicksort: Partition
6 
5 
7 
3 
4 
11 
8 
1 

We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
7 
3 
4 
11 
8 
1 

↑ 







We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
7 
3 
4 
11 
8 
1 


↑ 






We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
7 
3 
4 
11 
8 
1 


↑ 






We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
3 
7 
4 
11 
8 
1 



↑ 





We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
3 
4 
7 
11 
8 
1 




↑ 




We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
3 
4 
7 
11 
8 
1 




↑ 




We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
3 
4 
7 
11 
8 
1 




↑ 




We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
6 
5 
3 
4 
1 
11 
8 
7 





↑ 



We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
1 
5 
3 
4 
6 
11 
8 
7 





↑ 



We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
Quicksort: Partition
1 
5 
3 
4 
6 
11 
8 
7 





↑ 



We want to divide the array into smaller and larger parts and put the pivot in between them

If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

When we’re done, we’ll know where to put the pivot
> Click or hit ControlEnter to run the code above
Quicksort Runtime: Best Case
Let’s consider an array of size 8. In the best case, the pivot divides the array evenly at each step. So the analysis is similar to Mergesort:

Partition 1: 1 O(n) partition where n = 8 into two arrays of size 4

Partition 2: 2 O(n) partition where n = 4 into four arrays of size 2

Partition 3: 4 O(n) partition where n = 2 into eight arrays of size 1

So given n = 8, we have done 3 O(n) steps, or O(n log n).
But Trouble Lurks…
Quicksort Runtime: Worst Case
Let’s consider an array of size 8. In the worst case, the pivot is the maximum or minimum value in each step.

Partition 1: 1 O(n) partition where n = 8 into two arrays of size 7 and size 1

Partition 2: 1 O(n) partition where n = 7 into two arrays of size 6 and size 1

Partition 3: 1 O(n) partition where n = 6 into two arrays of size 5 and size 1

Partition 4: 1 O(n) partition where n = 5 into two arrays of size 4 and size 1

…etc…

So given n = 8, we have done n O(n) steps, or O(n^2)!
Quicksort: Worst Case Overview
8 
7 
6 
5 
4 
3 
2 
1 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
8 
7 
6 
5 
4 
3 
2 
1 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
7 
6 
5 
4 
3 
2 
1 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
7 
6 
5 
4 
3 
2 
1 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
6 
5 
4 
3 
2 
1 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
6 
5 
4 
3 
2 
1 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
6 
5 
4 
3 
2 
1 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
5 
4 
3 
2 
1 
6 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
5 
4 
3 
2 
1 
6 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
5 
4 
3 
2 
1 
6 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
4 
3 
2 
1 
5 
6 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Quicksort: Worst Case Overview
4 
3 
2 
1 
5 
6 
7 
8 

In the worst case the problem only gets 1 unit smaller in each step!
Avoiding Bad Pivots
Good Quicksort implementations try to avoid picking bad pivot values:

First value: fails if the array is sorted in reverse order

Last value: fails if the array in already sorted

Better idea: choose a random value, or the median of several values
Quicksort Runtime
Measure  Best Case  Worst Case  Average Case 

Time 
O(n log n) 
O(n^2) 
O(n log n) 
Space 
O(log n) 
O(n) 
O(log n) 
One advantage of Quicksort over Mergesort is that it can be done inplace without requiring extra space.
Sorting Summary: Input Dependence
Algorithm  Best Case  Worst Case 

Insertion Sort 
Already sorted 
Sorted backwards 
Merge Sort 
Doesn’t matter 
Doesn’t matter 
Quicksort 
Random 
Sorted 1 
(Note that most of these are implementation dependent.)
Sorting Summary: Runtime
Algorithm  Best Case  Worst Case  Average Case 

Insertion Sort 
O(n) 
O(n^2) 
O(n^2) 
Merge Sort 
O(n log n) 
O(n log n) 
O(n log n) 
Quicksort 
O(n log n) 
O(n^2) 
O(n log n) 
Sorting Summary: Space
Algorithm  Extra Memory 

Insertion Sort 
O(1) 
Merge Sort 
O(n) 
Quicksort 
O(log n), due to the recursive calls 
There Be Tradeoffs

If you have a very small array? Try insertion sort. It avoids the recursive calls made by merge sort and quick sort and is fastest on small arrays.

Do you want predictable performance? Try merge sort. It’s performance doesn’t vary based on its inputs, although it requires O(n) space.

Are you short on space? Try Quicksort. It’s bestcase performance is as good as merge sort but it can be done using much less memory.
Sorting Stability
We also refer to sorts as being either stable or unstable:

Stable sorts: two items with the same value cannot switch positions

Unstable sorts: two items with the same value may switch positions
Why Is Stability Important?
class Person {
int age;
String name;
}
Let’s say I wanted a list of all Person
s, sorted first by age and then by
name. How would I do that?

Sort first using the
name
field 
Then sort by the
age
field
If the sort is not stable I cannot do this, since the second sort will alter the results of the first.
What About Timsort?
Timsort is the adaptive sorting algorithm used by Python and now Java.

It’s far more complex than any of the algorithms we’ve discussed, but tries to take advantage of runs of alreadysorted values in the data.

Internally it uses both merge sort and insertion sort to sort smaller arrays and combine them together.

It’s an adaptive sort, meaning that it adjusts its behavior to features of the data.
A Fun Visualization
Questions About Sorting?
Announcements

I’m still holding office hours online, but nobody ever comes. Please drop in and say hi!