Try it yourself

Run this code directly in your browser. Click "Open in full editor" to experiment further.

Loading...

Click Run to see output

Or press Ctrl + Enter

How it works

Insertion Sort is the way most people naturally sort a hand of playing cards. 🃏

The Real-World Analogy

Imagine you're being dealt cards one at a time. You hold the cards you already have in your left hand (the sorted pile). Each new card you pick up, you slide left through your hand until it lands in the right spot. That's it — that's the whole algorithm.

How It Works

1. Treat the first element as a sorted list of size 1.

2. Take the next element (the "current card").

3. Walk leftward through the sorted part, sliding any larger element one step to the right.

4. Drop the current card into the gap you just opened.

5. Repeat until you've placed every card.

At every step, the left side of the array stays perfectly sorted — it just keeps growing by one.

Why Use It?

Tiny arrays: It's actually faster than fancy algorithms (quicksort, mergesort) for small inputs (~10–20 elements). Many real sorting libraries switch to insertion sort for small sub-arrays!

Nearly-sorted data: If your data is already mostly in order, insertion sort runs in nearly O(n) time. Bubble sort can match this, but insertion sort does fewer swaps.

Online sorting: You can sort data as it arrives, one element at a time, without seeing the whole list first.

Stable: Equal elements keep their original order — useful when sorting by multiple keys.

Time Complexity

Best case: O(n) — Already sorted! The inner while loop never runs.

Average case: O(n^2) — Random data means lots of sliding.

Worst case: O(n^2) — Reverse-sorted data: every new card has to travel all the way to the front.

Space Complexity: O(1) — Sorts in-place. No extra arrays needed.

Insertion Sort vs Bubble Sort

Both are O(n^2), but insertion sort usually wins in practice:

It does fewer comparisons on average.

It only writes to the array when necessary (bubble sort swaps constantly).

It's the algorithm humans actually use for small jobs — that's a good hint that it's intuitive and efficient at small scale.

Learn this one well — it's the sorting algorithm you'll use the most in your own head. 🧠

Related examples

Algorithms

Insertion Sort in Python