What is Insertion Sort?

Insertion Sort builds a sorted array one element at a time by shifting larger elements to the right and inserting each new element into its correct position within the sorted section.

Steps in Insertion Sort

Step-by-Step Process:
  1. Initialize the sorted part with the first element.
  2. Take each new element from the unsorted part and insert it in the correct position in the sorted part by shifting larger elements to the right.

Complexity

Worst Case: O(n²) - when the array is sorted in reverse.

Best Case: O(n) - when the array is already sorted.

Space Complexity: O(1) - it requires constant space.

Insertion Sort Visualization

for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}
Home