Insertion sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time by inserting each new element into its correct position in an already-sorted left portion of the list.

Quick Scoop: What Is Insertion Sort?

Insertion sort works like sorting playing cards in your hand: you pick one card at a time and insert it into the right place among the cards you’re already holding in order.

It keeps the left side of the array sorted and repeatedly inserts the next element from the right side into that sorted part.

How Insertion Sort Works (Step-by-step)

For an array like [5, 2, 4, 6, 1, 3]:

  1. Assume the first element is already sorted.
  2. Take the next element (the “key”) from the unsorted part.
  3. Compare the key with elements in the sorted part (moving left).
  4. Shift elements that are larger than the key one position to the right.
  1. Insert the key into the correct empty spot.
  2. Repeat until all elements are processed.

Example evolution:

  • Initial: [5, 2, 4, 6, 1, 3]
  • Step 1: [2, 5, 4, 6, 1, 3]
  • Step 2: [2, 4, 5, 6, 1, 3]
  • Step 4: [1, 2, 4, 5, 6, 3]
  • Final: [1, 2, 3, 4, 5, 6]

Pseudocode (Core Idea)

Generic pseudocode for insertion sort looks like this:

  • Start from index 1 to end:
    • key = array[i]
    • j = i - 1
    • While j >= 0 and array[j] > key: shift array[j] right
    • Insert key at array[j + 1]

This in-place approach only uses a few extra variables in addition to the array itself.

Time Complexity & When To Use It

  • Best case (already sorted list): O(n)O(n)O(n) comparisons, since elements never move left.
  • Average and worst case (random or reverse order): O(n2)O(n^2)O(n2) time due to many shifts.
  • Space complexity: in-place, so O(1)O(1)O(1) extra memory.

Insertion sort is good for:

  • Small arrays or lists.
  • Nearly sorted or partially sorted data.
  • Educational purposes to learn how sorting by shifting/insertion works.

It is not ideal for very large datasets compared to algorithms like merge sort or quicksort, which scale more efficiently.

Mini Forum-style Take

“Insertion sort is like tidying a small stack of papers on your desk: easy and intuitive for a few pages, but you wouldn’t use it to organize an entire library.”

In modern coding practice (as of mid‑2020s), insertion sort still shows up in interviews, textbooks, and sometimes as the inner routine of more advanced algorithms for small subarrays.

Meta description (SEO-style):
Insertion sort is a simple sorting algorithm that builds a sorted list one element at a time by inserting each item into its correct position, efficient for small or nearly sorted datasets.

Information gathered from public forums or data available on the internet and portrayed here.