Sorting

Insertion Sort

An intuitive comparison-based sorting algorithm that builds the sorted array one item at a time.

What is Insertion Sort?

Insertion Sort builds a sorted array one element at a time. It takes each incoming element from the unsorted section and inserts it into its correct relative position within the sorted section by shifting larger elements to the right.

Key Characteristics:

  • Stable sort.
  • In-place sort: O(1) memory.
  • Adaptive: extremely efficient for nearly sorted or small datasets.
  • Online: can sort data as it is received.

Complexity Analysis

Avg Time Complexity: O(N^2) average and worst case
Space Complexity: O(1) auxiliary space
Best Case: O(N) (pre-sorted array; no shifts)
Worst Case: O(N^2) (reverse sorted array; maximum shifts)

How it Works Step-by-Step

  1. Pick Key: Loop index i from 1 to N-1. Select key = array[i].
  2. Shifting Pointer: Set pointer j = i - 1.
  3. Shift elements: While j >= 0 and array[j] > key, shift array[j] to array[j+1] and decrement j.
  4. Insert Key: Place key at index j+1. Repeat for all elements.

Code Implementation

Worked Trace Example

Sorting [12, 11, 13, 5, 6]:
1. i=1 (key=11): compare 11,12. Shift 12 -> [12, 12, 13, 5, 6]. Insert 11 -> [11, 12, 13, 5, 6].
2. i=2 (key=13): compare 13,12 (no shift) -> [11, 12, 13, 5, 6].
3. i=3 (key=5): compare 5 with 13, 12, 11. Shift all -> [11, 11, 12, 13, 6] -> insert 5 -> [5, 11, 12, 13, 6].
4. i=4 (key=6): shift 13, 12, 11. Insert 6 -> [5, 6, 11, 12, 13].
Result: Sorted array [5, 6, 11, 12, 13].

Ready to Understand Insertion Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Insertion Sort Visualizer →