Faangprep Logo
Log inStart free
Browse curriculum

Insertion Sort

Insertion sort is an adaptive sorting algorithm that builds the sorted array one item at a time.

Intuition

Think of sorting playing cards in your hand. You pick up one card at a time and insert it into its correct position among the cards you're already holding.

Concept

  • Strategy: Split the list into sorted (left) and unsorted (right). Pick element from unsorted, shift larger elements in sorted right, insert element.
  • Adaptive: Runs in O(N) time if the input is already sorted.
  • Stable: Preserves the relative order of equal elements.

How it Works

Algorithm:

  1. Assume index 0 is sorted.
  2. Take element at index i (Key).
  3. Compare Key with elements at i-1, i-2....
  4. If element > Key, shift it right.
  5. Insert Key when smaller element found or start reached.

Step-by-Step Breakdown

Watch the visualization:

  • Blue Bar (Key): The element currently being inserted.
  • Red Bars: Elements being shifted to make space.
  • Green Bars: The sorted portion of the array.
Trace: [12, 11, 13, 5, 6]
Pass 1 (Insert 11)
STEP 1
12111356

Key is 11. Compare with sorted predecessor 12.

Result

Key: 11

STEP 2
12111356

Is 12 > 11? YES.

Result

Shift 12 ->

STEP 3
12121356

Move 12 to position 1. Reached start.

Result

[12, 12, ...]

STEP 4
11121356

Insert Key (11) at position 0.

Result

[11, 12, 13, ...]

When to Use

  • Small/Almost Sorted Data: Extremely efficient (O(N)) for nearly sorted arrays.
  • Online Sorting: Can sort data as it arrives (streaming).

When NOT to Use

  • Large Random Lists: O(N²) time complexity makes it slow.
  • Reverse Sorted: Worst-case scenario.

How to Identify

"Sort online", "Data is nearly sorted".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Selection Sort

Next

Merge Sort

Frequently Asked Questions

When is Insertion Sort most efficient?

Insertion Sort is highly efficient for small datasets and for arrays that are already substantially sorted (nearly-sorted data).

What is the time complexity of Insertion Sort?

The worst-case complexity is O(n²), but the best-case (for a sorted array) is O(n).

Is Insertion Sort an online algorithm?

Yes, it can sort a list as it receives it, making it ideal for streaming data setup.