Insertion Sort

Insertion Sort builds the final sorted array one element at a time. It takes each element from the unsorted portion and inserts it into its correct position in the sorted portion, similar to how you might sort playing cards in your hand.

Complexity Analysis

Best Case

O(n)

Average Case

O(n²)

Worst Case

O(n²)

Space Complexity

O(1)

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;

        // Move elements greater than key to one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }

        // Place key in its correct position
        arr[j + 1] = key;
    }
    return arr;
}

How Insertion Sort Works

Insertion Sort works like sorting playing cards in your hand. You take each new card and insert it into the correct position among the already sorted cards.

Algorithm Steps:

  1. Start with the second element (first is already "sorted")
  2. Store the current element as the "key" to be inserted
  3. Compare the key with the element immediately to its left
  4. If the key is smaller, shift the left element to the right
  5. Continue shifting elements until finding the correct position
  6. Insert the key into its proper position
  7. Repeat for all remaining elements

Key Characteristics:

  • Stable: Maintains relative order of equal elements
  • In-place: Requires only constant extra space O(1)
  • Adaptive: Very efficient on nearly sorted arrays
  • Online: Can sort elements as they come in
  • Simple: Intuitive and easy to implement

Real-World Applications:

  • Small datasets: Often used for small arrays (n ≤ 20)
  • Nearly sorted data: Best choice when data is mostly sorted
  • Online sorting: When you need to add elements incrementally
  • Hybrid algorithms: Used as base case in Timsort and Introsort

Performance Insights:

  • Best Case: O(n) when array is already sorted
  • Worst Case: O(n²) when array is reverse sorted
  • Adaptive Nature: Number of comparisons depends on input order
  • Shift Operations: Makes O(n²) shifts in worst case