2. Sorting

Bubble Sort

How it works: Repeatedly iterate through the list. Compare adjacent elements and swap them if they are in the wrong order. Repeat until no swaps are needed. Larger elements “bubble” to the end of the list each pass.

Why it’s correct: Each pass guarantees that the largest remaining unsorted element moves to its correct position. Repeating this process ensures that all elements are eventually sorted.

Runtime:

• Worst Case: $\mathcal{O}(n^2)$
• Best Case (already sorted, optimized with a swap check, i.e. if any swaps occurred and we can exit early): $\Omega (n)$

Selection Sort

$$\begin{array}{rl}j=5:(5,3,7,1,4)& \to (5,3,4,1,7)\\ j=4:(5,3,4,1,7)& \to (1,3,4,5,7)\\ j=3:(1,3,4,5,7)& \to (1,3,4,5,7)\\ j=2:(1,3,4,5,7)& \to (1,3,4,5,7)\\ j=1:(1,3,4,5,7)& \to (1,3,4,5,7)\end{array}$$

How it works: Repeatedly select the largest element from the unsorted portion and swap it with the last unsorted element $j$. Move the boundary $j$ of the sorted portion backward.

Why it’s correct: At each iteration, the selected element is guaranteed to be in its correct final position. Repeating this for all positions results in a fully sorted array.

Runtime: $\Theta (\sum 0\dots n)$ $=\Theta (n^2)$

Insertion Sort

$$\begin{array}{rl}j=2:(5,3,7,1,4)& \to (3,5,7,1,4)\\ j=3:(3,5,7,1,4)& \to (3,5,7,1,4)\\ j=4:(3,5,7,1,4)& \to (1,3,5,7,4)\\ j=4:(1,3,5,7,4)& \to (1,3,4,5,7)\end{array}$$

How it works: Build the sorted array one element at a time. Take the next element $j$ and insert it into the correct position in the already sorted portion by shifting larger elements to the right.

Why it’s correct: Each insertion maintains the sorted order of the left portion of the array. After processing all elements, the entire array is sorted.

Runtime:

• Worst Case (reverse sorted): $\mathcal{O}(n^2)$
• Average Case: $\Theta (n^2)$
• Best Case (already sorted): $\Omega (n)$

Note: We also saw in the lectures that we can implement InsertionSort using binary search. That reduces comparisons to $\mathcal{O}(n\log n)$. However, that also worsens our best case, already sorted, from $\Omega (n)$ to $\Omega (n\log n)$. The worst case is still $\mathcal{O}(n^2)$ because we still need to push back all other elements by just as much.

Merge Sort

public static void mergeSort(int[] A) {
	// Use only one temp array across all recursive calls
	int[] temp = new int[A.length];
	sort(0, A.length-1, A, temp);
}
 
private static void sort(int l, int r, int[] A, int[] temp) {
	if (l >= r) return;
	
	int m = (l + r) / 2;
	
	sort(l, m, A, temp);
	sort(m+1, r, A, temp);
	merge(l, m, r, A, temp);
}
 
private static void merge(int l, int m, int r, int[] A, int[] temp) {
	int curr = l, posL = l, posR = m+1;
	
	while (posL <= m && posR <= r) {
	    if (A[posL] <= A[posR]) temp[curr++] = A[posL++];
	    else temp[curr++] = A[posR++];
	}
	
	while (posL <= m) temp[curr++] = A[posL++];
	while (posR <= r) temp[curr++] = A[posR++];
	
	// Copy from temporary array into actual one
	for (int i=l; i<=r; i++) A[i] = temp[i];
}

How it works: Recursively divide the array into two halves until each half has one element. Merge the halves back together in sorted order by repeatedly taking the smaller element from the front of each half.

Why it’s correct: Merging two sorted arrays always produces a correctly sorted array. Recursively applying this process ensures the entire array is sorted.

Runtime: $\Theta (n\log n)$ Space complexity: $\Theta (n)$ b/c copying requires additional array. The recursion stack is asymptotically irrelevant.

Quicksort

How it works:

• Pick a pivot element
• Partition the array so that elements less than the pivot go to the left and elements greater go to the right.
• Recursively sort the left and right partitions.

Why it’s correct: Partitioning ensures all elements are on the correct side of the pivot. Recursively sorting the partitions guarantees the entire array is sorted.

Runtime:

• Average $\Theta (n\log n)$
• Worst case with horrible pivot $\mathcal{O}(n^2)$ Space Complexity: $\mathcal{O}(\log n)$ for recursion stack

Heapsort

How it works: Build a max-heap from the array. Repeatedly swap the root (largest element) with the last element of the heap and reduce the heap size by one. Restore the heap property (heapify) after each swap.

Why it’s correct: The max-heap ensures the largest element is always at the root. Removing it and heapifying the remaining elements repeatedly places elements in their correct final positions.

Runtime: $\Theta (n\log n)$ since you have to insert $n$ el. to make the heap and then extract $n$ el. Space Complexity: $O(1)$ auxiliary (in-place) Locality: Horrendous, therefore usually slower than Mergesort and Quicksort