DSA Tracker

Visualize

Insertion Sort

time O(n^2)space O(1)

The key insight: insertion sort builds the sorted array one element at a time, from left to right. In each pass, we take the next element and shift larger elements in the sorted prefix one position to the right, creating a hole where the new element belongs. This is like sorting playing cards in your hand: pick up one card, compare it to the ones already held, and insert it in the correct position.

Details

Animated on: Sort nums = [5, 2, 4, 6, 1, 3] in ascending order using insertion sort.

Problem:Insertion SortEasy

Sorting

step 1 / 33

5
[0]
2
[1]
4
[2]
6
[3]
1
[4]
3
[5]

i = 1: pick up arr[i] = 2 as the key; the sorted prefix so far is just [5] to the left of index 1.

  • i=1· arr[1] = 2
  • key=1· arr[1] = 2
Pseudocode
1FUNCTION insertionSort(arr):
2  n = the length of arr
3  FOR i from 1 to n-1:
4    key = arr[i]   (the value to insert)
5    j = i - 1
6    WHILE j >= 0 and arr[j] > key:
7      arr[j + 1] = arr[j]   (shift the bigger value one step right)
8      j = j - 1
9    arr[j + 1] = key   (drop key into the hole)

← / → step · space play · Home restart

Every step in words

Show all 33 steps
  1. i = 1: pick up arr[i] = 2 as the key; the sorted prefix so far is just [5] to the left of index 1.
  2. j = i - 1 = 0: compare arr[j] = 5 with key = 2; since 5 > 2, shift arr[j] rightward.
  3. arr[j + 1] = arr[j] = 5: shift element at index 0 right to index 1; the array now has a duplicate at index 1, and index 0 is vacated.
  4. j = j - 1 = -1: the while condition j >= 0 fails; we exit the loop and place key at arr[j + 1] = arr[0] = 2.
  5. arr[j + 1] = key = 2: place the saved key into the vacated position; the sorted prefix is now [2, 5].
  6. i = 2: pick up arr[i] = 4 as the key; the sorted prefix so far is [2, 5] to the left of index 2.
  7. j = i - 1 = 1: compare arr[j] = 5 with key = 4; since 5 > 4, shift arr[j] rightward.
  8. arr[j + 1] = arr[j] = 5: shift element at index 1 right to index 2; the array now has 5 at index 2, and index 1 is vacated.
  9. j = j - 1 = 0: compare arr[j] = 2 with key = 4; since 2 <= 4, the while condition fails and we exit the loop.
  10. arr[j + 1] = key = 4: place the saved key into the vacated position at index 1; the sorted prefix is now [2, 4, 5].
  11. i = 3: pick up arr[i] = 6 as the key; the sorted prefix so far is [2, 4, 5] to the left of index 3.
  12. j = i - 1 = 2: compare arr[j] = 5 with key = 6; since 5 <= 6, the while condition fails immediately.
  13. arr[j + 1] = key = 6: place the saved key into the vacated position at index 2; the sorted prefix is now [2, 4, 5, 6].
  14. i = 4: pick up arr[i] = 1 as the key; the sorted prefix so far is [2, 4, 5, 6] to the left of index 4.
  15. j = i - 1 = 3: compare arr[j] = 6 with key = 1; since 6 > 1, shift arr[j] rightward.
  16. arr[j + 1] = arr[j] = 6: shift element at index 3 right to index 4; the array now has 6 at index 4, and index 3 is vacated.
  17. j = j - 1 = 2: compare arr[j] = 5 with key = 1; since 5 > 1, shift arr[j] rightward.
  18. arr[j + 1] = arr[j] = 5: shift element at index 2 right to index 3; the array now has 5 at index 3, and index 2 is vacated. (Continue shifting.)
  19. j = j - 1 = 1: compare arr[j] = 4 with key = 1; since 4 > 1, shift arr[j] rightward.
  20. arr[j + 1] = arr[j] = 4: shift element at index 1 right to index 2; the array now has 4 at index 2, and index 1 is vacated.
  21. j = j - 1 = 0: compare arr[j] = 2 with key = 1; since 2 > 1, shift arr[j] rightward.
  22. arr[j + 1] = arr[j] = 2: shift element at index 0 right to index 1; the array now has 2 at index 1, and index 0 is vacated.
  23. j = j - 1 = -1: the while condition j >= 0 fails; exit the loop and place key at arr[j + 1] = arr[0] = 1.
  24. arr[j + 1] = key = 1: place the saved key into the vacated position at index 0; the sorted prefix is now [1, 2, 4, 5, 6].
  25. i = 5: pick up arr[i] = 3 as the key; the sorted prefix so far is [1, 2, 4, 5, 6] to the left of index 5.
  26. j = i - 1 = 4: compare arr[j] = 6 with key = 3; since 6 > 3, shift arr[j] rightward.
  27. arr[j + 1] = arr[j] = 6: shift element at index 4 right to index 5; the array now has 6 at index 5, and index 4 is vacated.
  28. j = j - 1 = 3: compare arr[j] = 5 with key = 3; since 5 > 3, shift arr[j] rightward.
  29. arr[j + 1] = arr[j] = 5: shift element at index 3 right to index 4; the array now has 5 at index 4, and index 3 is vacated. (Continue shifting.)
  30. j = j - 1 = 2: compare arr[j] = 4 with key = 3; since 4 > 3, shift arr[j] rightward.
  31. arr[j + 1] = arr[j] = 4: shift element at index 2 right to index 3; the array now has 4 at index 3, and index 2 is vacated. (Now check the next condition.)
  32. j = j - 1 = 1: compare arr[j] = 2 with key = 3; since 2 <= 3, the while condition fails and we exit the loop.
  33. arr[j + 1] = key = 3: place the saved key into the vacated position at index 2; the sorted prefix now covers the entire array [1, 2, 3, 4, 5, 6]. Sorting complete.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Insertion Sort in the editorAll Sorting problemsBack to roadmap