This is an in-pace sorting algorithm (\(O(1)\) space) that works for small input sizes.
Recall that a sorting algorithm sorts in place if only a constant number of elements of the input array are ever stored outside the array.
The invariant that insertion sort maintains is that at the \(i^{th}\) iteration, the first \(i\) elements in the array are sorted.
To maintain this, we need to do the following in the inner loop. We do this by looping within the first \(i\) elements till we reach the element where we can insert the \(i+1\) element.
The inner invariant can be stated as ensuring that in the \(i^{th}\) iteration, we need to ensure that all elements in the sub-list \([j+1, i]\) are greater than the \(j^{th}\) element. If this is not true, then we can remedy it by pushing the last element forward with a swap.
Here is how this algorithm can be illustrated using pseudocode:
procedure insertionSort(array A)
n = length(A)
// Iterate from the second element to the last
for i = 1 to n - 1
// Store the current element to be inserted
key = A[i]
// Start comparing key with elements to its left
j = i - 1
// Move elements of A[0..i-1], that are greater than key,
// to one position ahead of their current position
while j >= 0 and A[j] > key
A[j + 1] = A[j]
j = j - 1
// Insert the key into its correct position
A[j + 1] = key
end for
end procedureThis leads to an algorithm that sorts in worst case \(O(n^2)\) time. However, here are the different cases:
| Case | Time Complexity | Description |
|---|---|---|
| Best Case | O(n) | Occurs when the array is already sorted. The algorithm makes a single comparison for each element, resulting in linear time. |
| Average Case | O(n²) | Occurs when the elements are in a random or jumbled order. The number of comparisons and shifts grows quadratically with the input size. |
| Worst Case | O(n²) | Occurs when the array is sorted in reverse order. Every new element must be compared and swapped with all elements in the already sorted portion. |
In Java, this can be condensed down into the following algorithm. This is a classic insertion sort algorithm with a slightly different structure than you might typically see:
void insertionSort(int arr[], int n){
for (int i = 1; i < n; ++i) {
for (int j = i; j >= 1 && arr[j-1] > arr[j]; --j) {
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}The outer loop (for int i = 1; i < n; ++i) moves through the array from the second element to the end. The variable i represents the current element we're trying to insert into the already-sorted portion of the array (everything to the left of i).
The inner loop (for int j = i; j >= 1 && arr[j-1] > arr[j]; ++j) is where the insertion happens.
With --j, the element at position i gets swapped leftward repeatedly until it finds its correct position in the already-sorted portion of the array.
That's how insertion sort is supposed to work - you take each element and "bubble" it leftward into its proper place among the elements that came before it.
Because of its efficiency with small data, many advanced sorting algorithms like TimSort and IntroSort use insertion sort as a subroutine to sort small partitions of data.