Sorting Algorithms

Insertion Sort

Efficient algorithm for sorting a small number of algorithms. If the array is sorted, the runtime is reduced to $O(n)$.

High Level Idea: We go from left to right.

1. Find where x should go
2. Shift elements that are greater x
3. Insert x
4. Repeat

Insertion Sort Pseudocode#card

for i in range(1, len(A)):
	j = i # scan backward from i.
	while j > 0 and A[j - 1] > A[j]:
		# swap out-of-order elements.
		A[j], A[j - 1] = A[j - 1], A[j]
		j -= 1

Time Complexity

• Best Case: $O(n)$
• Average Case: $O(n^2)$
• Worst Case: $O(n^2)$

Space Complexity

• Worst Case: $O(n)$