DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
Sorting algorithms

Sorting

Insertion Sort

Builds a sorted prefix one element at a time: the next element (the key) is lifted out, larger elements of the prefix shift one step right, and the key drops into the gap.

Worst O(n²)Space O(1)Stable
Open visualizer

1Detailed explanation

Insertion sort works the way many people sort playing cards. The left part of the array is kept sorted; the next element (the key) is lifted out, larger elements of the sorted part shift one step to the right, and the key drops into the gap.

On nearly sorted data very few shifts are needed, so insertion sort runs in close to linear time. This is why hybrid sorts such as Timsort and introsort switch to insertion sort for small partitions.

It is stable (equal keys never jump over each other) and in-place.

2Pseudocode

procedure insertionSort(A)
  for i ← 1 to length(A) − 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
  return A

3Interactive visualization

Insertion Sortinteractive Open full visualizer
12
11
13
5
6
0
1
2
3
4
ComparingSwapping / movingCurrentSorted / finalFound / placed

Builds a sorted prefix one element at a time: the next element (the key) is lifted out, larger elements of the prefix shift one step right, and the key drops into the gap.

1 / 43

4Implementations

Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.

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

const arr = [12, 11, 13, 5, 6];
console.log("Sorted:", insertionSort(arr));

5Time and space complexity

Time
Best caseO(n)
Average caseO(n²)
Worst caseO(n²)
Space
AuxiliaryO(1)
InputO(n)
TotalO(n)

Time: Each key is compared with the sorted prefix until a smaller-or-equal element is found. On sorted input every key stops after 1 comparison → O(n). On reverse-sorted input key i shifts past all i prefix elements → 1+2+…+(n−1) = O(n²).

Space: Only key, i and j are stored; shifting is done inside the array, so auxiliary space is O(1).

6Common interview variations

  • Insertion sort on a linked list.
  • Binary insertion sort: find the position with binary search (fewer comparisons, same shifts).
  • Count inversions — equal to the number of shifts.
  • Sort an almost-sorted array where each element is at most k positions away.

On this page

  1. 01Detailed explanation
  2. 02Pseudocode
  3. 03Interactive visualization
  4. 04Implementations (JS · Python · Java · Go)
  5. 05Time and space complexity
  6. 06Common interview variations