SimuVedaAlgorithms Lab Open in the lab

Sorting / Beginner

Insertion Sort Visualizer

Keep the left part sorted. Take the next value (the key) and slide it left past every bigger value.

Start the Insertion Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n²)
Worst timeO(n²)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. The first value on its own is sorted. Grow the sorted part one value at a time. [5, 1, 4, 2, 8]
  2. Pick the key: 1.
  3. Is 5 bigger than 1?
  4. Yes. Shift 5 one step right. [1, 5, 4, 2, 8]
  5. Place 1 at index 0. Indexes 0 to 1 are now sorted.
  6. Pick the key: 4.
  7. Is 5 bigger than 4?
  8. Yes. Shift 5 one step right. [1, 4, 5, 2, 8]
  9. Is 1 bigger than 4?
  10. Place 4 at index 1. Indexes 0 to 2 are now sorted.
  11. Pick the key: 2.
  12. Is 5 bigger than 2?
  13. Yes. Shift 5 one step right. [1, 4, 2, 5, 8]
  14. Is 4 bigger than 2?
  15. Yes. Shift 4 one step right. [1, 2, 4, 5, 8]
  16. Is 1 bigger than 2?
  17. Place 2 at index 1. Indexes 0 to 3 are now sorted.
  18. Pick the key: 8.
  19. Is 5 bigger than 8?
  20. Place 8 at index 4. Indexes 0 to 4 are now sorted.
  21. Sorted. 7 comparisons and 4 shifts.

Try it with your own input →

Insertion sort in Java, Python, C++, C and JavaScript

void insertionSort(int[] a) {
  for (int i = 1; i < a.length; i++) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}
def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
void insertionSort(vector<int>& a) {
  for (int i = 1; i < (int)a.size(); i++) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}
void insertionSort(int a[], int n) {
  for (int i = 1; i < n; i++) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}
function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

In an interview

Very fast on nearly sorted data. Try the Nearly sorted preset and compare the shift count with Reversed.

More sorting