Welcome to Lesson 20!

Learning Objectives
By the end of this class, you should know...
• Sorting Algorithm Classification
• Bubble sort
• Merge sort
• Divide and Conquer

1. Sorting Algorithms
• Used to put list of values in order
• numerical, lexographic or other (how to compare two objects from the same class?)
• Typical run-times of sorting algorithms:
• Worst class of sorting algorithms: average O(n2) or above
• Best class of sorting algorithms: average O(n log n)
• Average of O(n) is not possible for comparison-based algorithms
• Why?
• Non-comparison based sorting algorithms can achieve better average results:
• Bucket sort: O(n + k)
• Recursive and non-recursive
• Comparison-based vs parallel
• Divide and conquer
• In-place algorithms (sorted without needing extra memory)
• Example: heap sort
• My experience with interviews and what I have heard:
•  #1 to know is merge sort
•  Should have merge sort and quick sort memorized when you interview
• Will ask you to know the merge sort algorithm for the final

 Algorithm Big-O Comparison-Based Parallel Divide and Conquer In-Place Bubble Sort n2 Yes No No Yes Heap Sort nlog(n) Yes No No Yes Merge Sort nlog(n) Yes No Yes No Quick Sort nlog(n) Yes No Yes No Bucket Sort n+k No Yes No No

2. BubbleSort Algorithm

• Compare all pairs of values
• Swap any pair where the first value is larger than the second value

Bubble Sort Animation Bubble Sort

Bubble Sort Pseudocode:

BubbleSort(A[], size)
for i = 0 to size - 1
for j = 0 to size - 1 //or size - i - 1
if A[j] > A[j+1]
A[j] <---> A[j+1] //swap

• Easy to write and remember
• Very sloooowww
• Run-times:
• Best-case: O(n)
• Average-case: O(n2)
• Worst-case: O(n2)
• Never used in real life applications

#### Why a Runtime of O(n) in the Best Case?

• An adaptation how the algorithm is implemented can achieve a Big-O runtime of O(n)
• In the best case, the array is already sorted. In this case, we should not execute the entire algorithm.
• If we can detect this case, we can end the algorithm early.
`BubbleSort(A[], size)    flag = true //array is sorted    for i = 0 to size - 1        for j = 0 to size - 1            if A[j] > A[j+1]               A[j] <---> A[j+1] //swap               flag = false //array was not sorted            if flag == true             break; //ends algorithm`

3. Merge Sort
• Recursive "Divide and Conquer" Algorithm
• Divide and Conquer is a common approach to problems in Computer Science
• Divide (the problem into a small number of pieces)
• Conquer (solve each piece, by applying divide-and-conquer recursively to it)
• Combine (the pieces together into a global solution)
• Merge Sort is one of the best known Divide and Conquer Algorithms
• Divide: Split A down the middle into two subsequences, each of size roughly n/2.
• Conquer: Sort each subsequence (by calling MergeSort recursively on each).
• Combine: Merge the two sorted subsequences into a single sorted list.
• The dividing process ends when we have split the subsequences down to a single item.
• A sequence of length one is trivially sorted.
• We can visualize Merge Sort's Divide and Conquer approach through the image below:

Merge Sort Performed on an Array Merge Sort Animation Merge Sort Pseudocode

MergeSort(A[], low, high)
if (low < high)
middle = (low + high) / 2 //midpoint formula
MergeSort(A[], low, middle)
MergeSort(A[], middle+1, high)
Merge(A[], low, middle, high)

Merge(A[], low, mid, high)
l = low
m = mid + 1
index = low //current index of result array
result[low...high] //will store sorted values
while (l <= mid AND m <= high) //while both subarrays are non empty
if(A[l] < A[m]) //A[l] is smaller value so copy into result
result[index] = A[l]
index++
l++
else
result[index] = A[m]
index++
m++
while (l <= mid) //right subarray is empty so copy over all of left side values
result[index] = A[l]
index++
l++
while (m <= high) //left subarray is empty so copy over all right side values
result[index] = A[m]
index++
m++
Copy(A, result) //copy contents of result into original Array A

• Note: The use of the temporary array result here is a necessary evil, as merge sort requires the use of a temporary array at some point in the algorithm.
• It is one of the shortcomings of MergeSort, compared to some of the other efficient sorting algorithms.
• In other words, it is not an "In Place Algorithm"
• In contrast to Heap Sort, where the array is sorted without requiring extra memory
• This version of mergeSort minimizes the creation of temporary arrays.
Order Of Steps

Time Complexity of Merge Sort
• O(n logn) - in Best, Worst, and Average Cases

Merge Sort with Cards

Wrap Up
• Answer the review questions for this lesson on Canvas

~ Have a Great Day! ~