Sorting

Insertion Sort

What is Insertion Sort?

Insertion Sort grows a sorted section of the array one element at a time, which is basically how most people sort a hand of playing cards — pick up the next card and slide it into the spot where it belongs among the cards you've already arranged.

How Does It Work?

Consider this unsorted array: [7, 3, 5, 2, 1]

  1. First Element (7):
    • Already "sorted" as the first item
    • → [7, 3, 5, 2, 1]
    key7031522314
  2. Second Element (3):
    • Insert before 7
    • → [3, 7, 5, 2, 1]
    insert here70key31522314
  3. Third Element (5):
    • Insert between 3 and 7
    • → [3, 5, 7, 2, 1]
    30insert here71key522314
  4. Fourth Element (2):
    • Insert at beginning
    • → [2, 3, 5, 7, 1]
    insert here305172key2314
  5. Fifth Element (1):
    • Insert at beginning
    • → [1, 2, 3, 5, 7]
    insert here20315273key14
Key (being inserted)Shifts rightSorted portion

The algorithm maintains a "sorted sublist" that grows with each iteration.

Algorithm Steps

  1. Start with the second element (consider first element as sorted)
  2. Pick the next element (key) from the unsorted portion
  3. Compare the key with elements in the sorted portion:
    • Shift elements greater than the key one position right
    • Stop when you find an element ≤ the key
  4. Insert the key in its correct position
  5. Repeat until all elements are processed

Time Complexity

  • Best Case: Already sorted array → O(n) (only comparisons, no shifts).
  • Average Case: Randomly ordered array → O(n²).
  • Worst Case: Reverse sorted array → O(n²) (maximum comparisons and shifts).

Time Complexity Analysis

Advertisement

Advantages

  • Efficient for small datasets (often faster than more complex algorithms for n ≤ 10)
  • Stable (doesn't change relative order of equal elements)
  • Adaptive (performs well with partially sorted data)
  • Online (can sort as it receives input)

Insertion Sort is often used when the data is nearly sorted (where it approaches O(n) time) or when the dataset is small. Some hybrid algorithms like TimSort use Insertion Sort for small subarrays due to its low overhead.

Daily DSA Challenge by Scale Engineer

Visualize how Insertion Sort builds the final sorted array.

Speed:1x
Comparisons:
0
Shifts:
0

Array Visualization

Generate or enter an array to begin

Test Your Knowledge before moving forward!

Insertion Sort Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • Earn stars based on your final score (max 5 stars)

Insertion Sort Implementation

// Insertion Sort in JavaScript
function insertionSort(arr) {
  // Start from the second element (index 1)
  for (let i = 1; i < arr.length; i++) {
    // Current element to be inserted
    let current = arr[i];
    // Compare with the sorted portion
    let j = i - 1;
    
    // Shift elements greater than current to the right
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    // Insert the current element in correct position
    arr[j + 1] = current;
  }
  return arr;
}

// Usage example
const unsortedArray = [12, 11, 13, 5, 6];
console.log("Unsorted array:", unsortedArray);
const sortedArray = insertionSort(unsortedArray);
console.log("Sorted array:", sortedArray);

Done With the Learning

Mark Insertion Sort as done and view it on your dashboard

Explore Sorting Algorithms

Selection Sort

Bubble Sort

Merge Sort

Quick Sort

Heap Sort