Sorting Algorithm

Insertion Sort

Builds a sorted section one element at a time by taking the next value and inserting it into its correct position among the already-sorted elements — exactly how most people sort a hand of playing cards.

BestO(n)
AverageO(n²)
WorstO(n²)
SpaceO(1)
StableYes

Try It — Animated Flow

29
8
44
15
3
37
21
Insertion sort grows a sorted section on the left, one element at a time — like sorting a hand of playing cards.
Step 1 / 25
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Sorting a hand of cards
The exact mental model most people already use: pick up the next card and slide it into its correct spot among the ones you're holding.
Live-updating leaderboards
When a single new score arrives, insertion sort drops it into an already-sorted list in O(n) — far cheaper than re-sorting everything.
Online / streaming data
It's an 'online' algorithm — it can sort data as it arrives, one element at a time, without needing the whole dataset up front.
Small sub-arrays in hybrid sorts
Production sorts like Timsort and introsort switch to insertion sort for small partitions because it beats quicksort/mergesort overhead below ~16 elements.

Trade-offs

Reach for it when
  • The array is small or already nearly sorted
  • Data arrives incrementally and must stay sorted
  • You need a stable, in-place, simple sort
Avoid it when
  • The dataset is large and mostly unordered
  • You need guaranteed O(n log n) performance
  • You need a general-purpose production sort (use Arrays.sort / Collections.sort)