Insertion sort is a simple sorting algorithm which starts by splitting the input array into two parts, a sorted part and an unsorted part, the sorted part bigger than the first element in the unsorted part is then shifted forwards one spot until there's a spot for the first element of the unsorted part to be placed within the sorted part.

// Assumes arr[0..p-1] are in sorted order
void slide(vector<int>& arr, int p) {
	int temp = arr[p];
	int j = p;
	
	while (j > 0 && arr[j-1] > temp) {
		arr[j] = arr[j-1];
		
		j--;
	}
	
	arr[j] = temp;
}

void insertionSort(vector<int>& arr) {
	for (int i = 0; i < arr.size(); i++) {
		slide(arr, i);
	}
}

Analysis

Runtime Complexity

Looking at the two loops, we can see that the first loop always iterates from 0 to arr.size(), the inner function on the other hand iterates backwards from i to 0. Using this knowledge we can construct a formula for the runtime

where = arr.size()

Correctness

Loop Invariant: Before iteration i of the for loop, arr[0..i-1] contains the i smallest elements of arr in ascending order.

Base Case: i = 0

• Before executing the iteration for i=0, the invariant states that arr[0..-1] contains the 0 smallest elements of arr in ascending order.
• Since the interval arr[0..-1] contains no elements the invariant holds in the base case. Inductive Step: i = k, 0 ≤ k < arr.size()
• Assume the loop invariant holds prior to processing index k, i.e. arr[0..k-1] contains the k smallest elements of arr in ascending order.
• Calling slide(arr, k) requires arr[0..k-1] to be sorted, which is guaranteed by the invariant.
• From the proof of slide, we know that afterwards arr[0..k] is sorted.
• Thus after processing index k, arr[0..k] contains the k+1 smallest elements of arr in ascending order and the loop invariant holds. Termination: i = arr.size()
• Invariant property states that arr[0..arr.size()-1] contains the arr.size() smallest elements of arr in ascending order.
• This interval contains the entire array, and thus the entire array is now in sorted order.
• Since arr.size() is finite, and i increments each iteration towards arr.size(), the program must terminate.