Insertion Sort

Insertion sort builds the final sorted array one element at a time. It takes each element from the unsorted part of the array and inserts it into its correct position within the already-sorted part. Think of how you sort playing cards in your hand: you pick up cards one at a time and insert each new card into its correct spot among the cards you’re already holding, shifting the others over as needed. At every step, the left portion of the array is always fully sorted. We take the next element, and slide it left past anything bigger than it, until it lands in the right spot.

Step-by-Step Example

Let’s sort the following array from smallest to largest:

Step 1 — Insert 3

We pick up 3 (highlighted in red) and compare it against the sorted region to its left.

Step 2 — Insert 8

Step 3 — Insert 1

This one needs to move all the way to the front.

Step 4 — Insert 4

✅ Final sorted array:

Try it yourself!

Important note!

Insertion sort is not suitable for large random datasets/arrays. However, it performs rather well when the arrays provided are nearly-sorted (best-case scenario). In practice, it is usually used internally by some hybrid sorting algorithms for small sub-arrays.