Sort a singly linked list using insertion sort.

Why Timsort uses Insertion Sort for small blocks

Why do production runtime engines (Python, Java Array.sort) use Insertion Sort for small arrays?

Sort Nearly Sorted / K-Sorted Array

Sort an array where each element is at most K positions away from its target sorted position.

Searching & Sorting AlgorithmsBeginner LevelStudy Time: 15 mins

Insertion Sort Algorithm

Insertion Sort builds a sorted array slice incrementally by picking unsorted elements and inserting them into their correct position within the sorted prefix.

Insertion Sort Visualizer

Array loaded. Trigger Insertion Sort to visualize element shifting.

40

[0]

20

[1]

50

[2]

10

[3]

30

[4]

25

[5]

Speed:

Insertion Sort Card Slide Trace

Sample Input:Input Array: [12, 11, 13, 5, 6]

Step 1

Insert Element 11

Key = 11. Compare 11 with sorted prefix [12]. 12 > 11, shift 12 right and place 11 at index 0.

[12, 11, 13, 5, 6] -> Shift 12 -> Insert 11 -> [11, 12, 13, 5, 6]

Sorted prefix expands to [11, 12].

Step 2

Insert Element 13

Key = 13. Compare 13 with 12. 13 > 12 -> 13 is already in correct position.

[11, 12, 13, 5, 6] -> No shift needed -> [11, 12, 13, 5, 6]

Sorted prefix expands to [11, 12, 13].

Step 3

Insert Element 5

Key = 5. Compare and shift 13, 12, 11 right. Place 5 at index 0.

[11, 12, 13, 5, 6] -> Shift [11,12,13] -> Insert 5 -> [5, 11, 12, 13, 6]

Inserts element into sorted position in O(N) shifts.

Real-world analogy: Organizing Bridge Hand Cards

Key

Hover over items for details

Hold cards in one hand. Pick cards from the table one by one and slide each card into its correct spot among the cards in your hand.

Key= The current item being inserted into the sorted subarray.

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapInsertion Sort: O(N²) Quadratic Time

Hover curves to inspect classes

Time Steps (N=500)

250,000 steps (Quadratic)

O(N²) Quadratic Time

Space Footprint

O(1) In-Place Space

Memory growth rate as N expands.

Performance Rank

Heavy Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
Best Case (Nearly Sorted)	O(N)	O(1)
Worst Case	O(N²)	O(1)

Code implementations

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}