Insertion Sort

Building the sorted list one item at a time

Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Key Index

Comparisons

Shifts

Press "Start Sorting" to begin

Unsorted

Comparing

Key Element

Shifting

Sorted Sublist

Speed

Deeper Analysis

Insertion Sort is an adaptive algorithm, meaning it becomes faster if the input is already partially sorted. In the best case (already sorted array), it runs in $O(n)$ time.

Online Sorting

One of its greatest strengths is that it can sort a list as it receives it. It doesn't need the entire dataset at the beginning.

Practical Use

Many advanced algorithms like Timsort use Insertion Sort for small subarrays because of its low overhead and stability.

Complexity

Best Case$O(n)$

Average/Worst Case$O(n^2)$

Space Complexity$O(1)$

StableYes

Algorithm Logic

Pseudocode

JavaScript

1for (i = 1; i < n; i++) {
2  key = arr[i];
3  j = i - 1;
4  while (j >= 0 && arr[j] > key) {
5    arr[j + 1] = arr[j];
6    j--;
7  }
8  arr[j + 1] = key;
9}

Fun Fact

Professional computer science researchers found that Insertion Sort is actually the most efficient algorithm for arrays with fewer than 10-20 elements.

Implementations

Python (Clean)

Pseudocode

Python

1def insertion_sort(arr):
2    for i in range(1, len(arr)):
3        key = arr[i]
4        j = i - 1
5        # Move elements of arr[0..i-1], that are
6        # greater than key, to one position ahead
7        # of their current position
8        while j >= 0 and key < arr[j]:
9            arr[j + 1] = arr[j]
10            j -= 1
11        arr[j + 1] = key
12    return arr

JavaScript ES6

Pseudocode

JavaScript

1const insertionSort = (arr) => {
2  for (let i = 1; i < arr.length; i++) {
3    let key = arr[i];
4    let j = i - 1;
5    
6    while (j >= 0 && arr[j] > key) {
7      arr[j + 1] = arr[j];
8      j = j - 1;
9    }
10    arr[j + 1] = key;
11  }
12  return arr;
13};

Deeper Analysis

Insertion Sort is an adaptive algorithm, meaning it becomes faster if the input is already partially sorted. In the best case (already sorted array), it runs in $O(n)$ time.

Online Sorting

One of its greatest strengths is that it can sort a list as it receives it. It doesn't need the entire dataset at the beginning.

Practical Use

Many advanced algorithms like Timsort use Insertion Sort for small subarrays because of its low overhead and stability.

Implementations

Python (Clean)

Pseudocode

Python

1def insertion_sort(arr):
2    for i in range(1, len(arr)):
3        key = arr[i]
4        j = i - 1
5        # Move elements of arr[0..i-1], that are
6        # greater than key, to one position ahead
7        # of their current position
8        while j >= 0 and key < arr[j]:
9            arr[j + 1] = arr[j]
10            j -= 1
11        arr[j + 1] = key
12    return arr

JavaScript ES6

Pseudocode

JavaScript

1const insertionSort = (arr) => {
2  for (let i = 1; i < arr.length; i++) {
3    let key = arr[i];
4    let j = i - 1;
5    
6    while (j >= 0 && arr[j] > key) {
7      arr[j + 1] = arr[j];
8      j = j - 1;
9    }
10    arr[j + 1] = key;
11  }
12  return arr;
13};