Insertion Sort

sorting · O(n²) avg

5

Configure inputs and press Visualize to begin.

64
34
25
12
22
11
90
45
Default
Comparing
Swap
Pivot
Sorted
Found
Pseudocode & Implementations
2 approaches

Shift elements right to make room. Best case O(n) on sorted input.

INSERTION-SORT(A):
  FOR i = 1 TO n-1:
    key = A[i]
    j = i - 1
    WHILE j >= 0 AND A[j] > key:
      A[j+1] = A[j]   // shift right
      j = j - 1
    A[j+1] = key      // place key
  RETURN A
Complexity Analysis

Time Complexity

Best Case
LinearO(n)
Average
QuadraticO(n²)
Worst Case
QuadraticO(n²)
Space (aux)
ConstantO(1)
StableIn-placecomparisonadaptivestable
About

Builds a sorted array one element at a time by inserting each element into its correct position in the already-sorted portion.

Key Insight

Adaptive: performs well on nearly-sorted data. Online algorithm that works on streaming input.

Use Cases

Nearly sorted dataOnline sortingSmall arraysHybrid algorithm base