What is Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works similarly to how you might sort playing cards in your hands - you take each new card and insert it into its proper position among the already sorted cards.

How Does It Work

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

First Element (7): Already "sorted" as the first item
→ [7, 3, 5, 2, 1]
Second Element (3): Insert before 7
→ [3, 7, 5, 2, 1]
Third Element (5): Insert between 3 and 7
→ [3, 5, 7, 2, 1]
Fourth Element (2): Insert at beginning
→ [2, 3, 5, 7, 1]
Fifth Element (1): Insert at beginning
→ [1, 2, 3, 5, 7]

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

Algorithm Steps

Start with the second element (consider first element as sorted)
Pick the next element (key) from the unsorted portion
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
Insert the key in its correct position
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).

Space Complexity

Like Bubble Sort, Insertion Sort is in-place and requires only O(1) additional space.

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.

Visualize how Insertion Sort builds the final sorted array one element at a time.

Insertion Sort Visualizer