Skip to main content

​
Overview

Insertion Sort builds the sorted array one element at a time by repeatedly taking the next unsorted element and inserting it into its correct position within the sorted portion. It’s similar to how most people naturally sort playing cards in their hands.

​
Complexity

  • Time Complexity:
    • Best case: O(n) - when array is already sorted
    • Average case: O(n²)
    • Worst case: O(n²) - when array is reverse sorted
  • Space Complexity: O(1) - sorts in-place
  • Stable: Yes - maintains relative order of equal elements

​
Implementation

Here’s the actual implementation from the Sorting Algorithms Visualiser: 
void InsertionSort(std::vector<int>& nums) {
	int tmpNum, minIndex;
	for (int i = 0; i < nums.size(); i++) {
		tmpNum = nums[i];
		minIndex = i;
		while (minIndex > 0 && tmpNum < nums[minIndex - 1]) {
			nums[minIndex] = nums[minIndex - 1];
			minIndex -= 1;
			HighlightRectangles(i, minIndex, -1);
			std::this_thread::sleep_for(std::chrono::nanoseconds(SORT_DELAY));
		}
		nums[minIndex] = tmpNum;
	}
	Verify(nums);
	return;
}

​
How It Works

  1. Iterate through array: Starting from index 0, consider each element
  2. Save current element: Store nums[i] in tmpNum
  3. Find insertion position: Use a while loop to shift elements right
    • Compare tmpNum with elements to the left
    • Shift larger elements one position to the right
    • Decrement minIndex to move left
  4. Insert element: Place tmpNum at the correct position minIndex
  5. Verification: After sorting, highlight each element to confirm sorted order

​
Step-by-Step Example

For the array [5, 2, 4, 6, 1]: Step 1 (i=0): [5] - first element is already “sorted” Step 2 (i=1): Consider 2
  • tmpNum = 2, compare with 5
  • Shift 5 right → [5, 5, 4, 6, 1]
  • Insert 2 → [2, 5, 4, 6, 1]
Step 3 (i=2): Consider 4
  • tmpNum = 4, compare with 5
  • Shift 5 right → [2, 5, 5, 6, 1]
  • Insert 4 → [2, 4, 5, 6, 1]
Step 4 (i=3): Consider 6
  • tmpNum = 6, already in correct position
  • [2, 4, 5, 6, 1]
Step 5 (i=4): Consider 1
  • Shift 6, 5, 4, 2 all right
  • Insert 1 at beginning → [1, 2, 4, 5, 6]

​
Watch It in Action

When running the visualiser, you’ll see:
  • Red highlight (highlight1): The original position i of the element being inserted
  • Green highlight (highlight2): The current position minIndex being evaluated
  • Blue highlight: Used during verification phase
As the algorithm runs, you’ll see elements shifting to the right (the green highlight moves left) until the correct insertion position is found. The visualization shows the “searching backward” behavior characteristic of insertion sort.
The visualization (line 107) highlights the original position in red and the current comparison position in green, making it easy to see elements being “inserted” into their correct position.

​
Best Use Cases

  • Small datasets: Very efficient for arrays with fewer than 10-20 elements
  • Nearly sorted data: Excellent performance when data is almost sorted (approaches O(n))
  • Online sorting: Can sort data as it arrives (doesn’t need entire dataset upfront)
  • Stable sorting required: Maintains relative order of equal elements
  • Memory constraints: Requires only O(1) additional space

​
Advantages

✓ Simple implementation ✓ Efficient for small datasets ✓ Adaptive - efficient for nearly sorted data ✓ Stable sorting algorithm ✓ In-place sorting (O(1) space) ✓ Online algorithm - can sort as it receives data

​
Disadvantages

✗ O(n²) comparisons and swaps in average and worst case ✗ Inefficient for large, unsorted datasets ✗ Many shifts required for reverse-sorted arrays
Despite its quadratic worst-case time complexity, Insertion Sort is often faster than more complex algorithms like Quick Sort for small arrays (typically n < 10-20). Many optimized sorting implementations use Insertion Sort for small subarrays.

Build docs developers (and LLMs) love

Get started for freeTalk to us