Insertion Sort
Insertion sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works much the way you might sort a hand of playing cards: pick up each card and slide it into the correct position among the cards you have already sorted. It is efficient for small datasets and nearly-sorted arrays, and its adaptive nature makes it a practical choice in many real-world scenarios.
How Insertion Sort Works
Insertion sort iterates through the array starting from the second element. For each element (called the "key"), it compares the key with elements in the already-sorted portion to its left and shifts larger elements one position to the right to make room. The key is then inserted into its correct position.
Step-by-step process:
- Start with the second element: The first element is trivially sorted. Pick the second element as the first key.
- Extract the key: Remove the current element (the key) from its position. This creates a gap in the array.
- Compare and shift: Moving right to left through the sorted portion, compare each element with the key. If the element is greater than the key, shift it one position to the right.
- Insert the key: Once you find an element smaller than or equal to the key (or reach the beginning of the array), insert the key into the gap.
- Repeat: Move to the next unsorted element and repeat the process until the entire array is sorted.
- Adaptive behavior: If the array is already nearly sorted, very few shifts are needed on each pass. In the best case (already sorted), insertion sort only makes n-1 comparisons and zero shifts, achieving O(n) time complexity.
Insertion sort is stable (equal elements retain their original relative order), in-place (uses O(1) extra memory), and adaptive (performs better when the input is partially sorted). These properties make it an excellent choice for small arrays, and it is often used as the base case in hybrid sorting algorithms like Timsort.
Interactive Visualization
Watch how insertion sort picks each key element and inserts it into the sorted portion. The purple bar is the key being inserted, yellow bars indicate elements shifting right, and green bars are in the sorted portion.
Code Implementation
Below is an insertion sort implementation in three languages. The algorithm picks each element from the unsorted portion and shifts larger elements to the right until the correct insertion position is found.
def insertion_sort(arr):
"""Sort array using insertion sort."""
n = len(arr)
for i in range(1, n):
key = arr[i]
# Shift elements greater than key to the right
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# Insert the key at its correct position
arr[j + 1] = key
return arr
# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90, 45]
print("Unsorted:", numbers)
print("Sorted: ", insertion_sort(numbers))
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
// Shift elements greater than key to the right
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert the key at its correct position
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] numbers = {64, 34, 25, 12, 22, 11, 90, 45};
System.out.print("Unsorted: ");
printArray(numbers);
insertionSort(numbers);
System.out.print("Sorted: ");
printArray(numbers);
}
private static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) System.out.print(", ");
}
System.out.println();
}
}
#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
// Shift elements greater than key to the right
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert the key at its correct position
arr[j + 1] = key;
}
}
void printArray(const vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
cout << arr[i];
if (i < arr.size() - 1) cout << ", ";
}
cout << endl;
}
int main() {
vector<int> numbers = {64, 34, 25, 12, 22, 11, 90, 45};
cout << "Unsorted: ";
printArray(numbers);
insertionSort(numbers);
cout << "Sorted: ";
printArray(numbers);
return 0;
}
Complexity Analysis
Insertion sort's performance varies significantly based on the initial order of elements. Its adaptive nature means it excels on nearly-sorted data, achieving linear time in the best case. For random or reverse-sorted data, it degrades to quadratic time due to the number of shifts required.
| Metric | Complexity | Notes |
|---|---|---|
| Best Case Time | O(n) | Array is already sorted; only n-1 comparisons, no shifts |
| Average Case Time | O(n²) | Elements are in random order; approximately n²/4 comparisons and shifts |
| Worst Case Time | O(n²) | Array is sorted in reverse order; maximum shifts on every pass |
| Space Complexity | O(1) | In-place sorting; only uses a single temporary variable for the key |
| Stable | Yes | Equal elements maintain their relative order (shifts only on strict inequality) |
Quiz
Test your understanding of insertion sort with these questions.
Q1. What is the best-case time complexity of insertion sort?
Q2. During insertion sort, what happens to elements that are greater than the key?
Q3. After 3 passes of insertion sort on the array [50, 30, 40, 10, 20], what is the state of the array?
Q4. Why is insertion sort considered "adaptive"?
Q5. Which of the following is a key advantage of insertion sort over merge sort?