Sorting Algorithms
> Click or hit ControlEnter to run the code above
Sorting Algorithms
Sorting algorithms bring together several of the things that we have discussed recently:

Imperative programming

BigO algorithm runtime analysis

Recursion
Sorting Matters
Sorting is often a building block for many other algorithms.

Searching is more efficient if the data is sorted first

Sorting can be used to detect duplicates

Sorting is often used to produce a canonical representation of data or for presentation to human users
In Memory of Jim Gray, Turing Award Winner
Jim Gray was a pioneer in the fields of databases and data processing.
He vanished at seat in 2007 and, despite a worldwide crowdsourced effort to locate his boat, was never found.
Speaking of the Turing Award…
There Are Many Sorting Algorithms
And we won’t discuss them all…

Insertion sort (today)

Selection sort (lab)

Merge sort (lecture)

Quicksort (lecture)

Bubble sort (lab)

And even new ones, like Timsort (circa 2002)
Sorting Basics

We’ll discuss sorting on arrays which allow random access, although many algorithms will also work on lists.

We’ll be sorting in ascending order, although obviously descending order sorts are also possible.

We can sort anything that we can compare—but we’ll mostly be sorting integers.
Analyzing Sorting Algorithms
Since sorting algorithms handle data, we care about both time and space complexity.

Time complexity: how long does it take?

Space complexity: how much space is required?
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.
Merge Sort: Overview




1 
8 
9 
12 




2 
5 
7 
10 









Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




1 
8 
9 
12 




2 
5 
7 
10 









Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





2 
5 
7 
10 
1 








Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





2 
5 
7 
10 
1 








Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





5 
7 
10 

1 
2 







Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





5 
7 
10 

1 
2 







Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





7 
10 


1 
2 
5 






Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





7 
10 


1 
2 
5 






Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





10 



1 
2 
5 
7 





Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




8 
9 
12 





10 



1 
2 
5 
7 





Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




9 
12 






10 



1 
2 
5 
7 
8 




Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




9 
12 






10 



1 
2 
5 
7 
8 




Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 







10 



1 
2 
5 
7 
8 
9 



Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 







10 



1 
2 
5 
7 
8 
9 



Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 











1 
2 
5 
7 
8 
9 
10 


Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview




12 











1 
2 
5 
7 
8 
9 
10 


Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Merge Sort: Overview
















1 
2 
5 
7 
8 
9 
10 
12 

Merge sort harnesses the fact that it is easy to merge two alreadysorted arrays
Announcements

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.