Insertion Sort — VisualAlgorithms Docs

How it works

Insertion Sort builds the sorted portion one element at a time. It takes the next unsorted element and shifts larger sorted elements one position right until the correct slot opens up, then drops the element in.

Because it only moves elements that are actually out of place, it is genuinely adaptive: nearly-sorted input runs in close to O(n).

Implementation

      
 function insertionSort(arr, stats) {
  const n = arr.length;
  const sorted = new Set([0]);
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    compare(i, j, {
      sorted
    });
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      swap(j, j + 1, {
        sorted
      });
      j--;
    }
    arr[j + 1] = key;
    markSorted(i);
    swap(j + 1, j + 1, {
      sorted
    });
    checkpoint(i, n);
  }
}
 from types import SimpleNamespace

def insertionSort(arr, stats):
    sorted = set([0])
    for i in range(1, n):
        key = arr[i]
        j = (i - 1)
        compare(i, j, SimpleNamespace(sorted=sorted))
        while ((j >= 0) and (arr[j] > key)):
            arr[(j + 1)] = arr[j]
            swap(j, (j + 1), SimpleNamespace(sorted=sorted))
            j -= 1
        arr[(j + 1)] = key
        markSorted(i)
        swap((j + 1), (j + 1), SimpleNamespace(sorted=sorted))
        checkpoint(i, n)
 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int sorted = 0;
    for(int i=1; i<n; i++) {
        int key = arr[i];
        int j = (i - 1);
        compare(i, j, {sorted: sorted});
        while(((j >= 0) && (arr[j] > key))) {
            arr[(j + 1)] = arr[j];
            swap(j, (j + 1), {sorted: sorted});
            j--;
        }
        arr[(j + 1)] = key;
        markSorted(i);
        swap((j + 1), (j + 1), {sorted: sorted});
        checkpoint(i, n);
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    int sorted = 0;
    for(int i=1; i<n; i++) {
        int key = arr[i];
        int j = (i - 1);
        compare(i, j, {sorted: sorted});
        while(((j >= 0) && (arr[j] > key))) {
            arr[(j + 1)] = arr[j];
            swap(j, (j + 1), {sorted: sorted});
            j--;
        }
        arr[(j + 1)] = key;
        markSorted(i);
        swap((j + 1), (j + 1), {sorted: sorted});
        checkpoint(i, n);
    }
} #include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int sorted = 0;
    for(int i=1; i<n; i++) {
        int key = arr[i];
        int j = (i - 1);
        compare(i, j, {sorted: sorted});
        while(((j >= 0) && (arr[j] > key))) {
            arr[(j + 1)] = arr[j];
            swap(j, (j + 1), {sorted: sorted});
            j--;
        }
        arr[(j + 1)] = key;
        markSorted(i);
        swap((j + 1), (j + 1), {sorted: sorted});
        checkpoint(i, n);
    }
} 

Advantages

Excellent on small or nearly-sorted arrays — often the fastest choice for tiny inputs.
Stable and in-place with O(1) extra memory.
Online: can sort a stream as elements arrive.

Disadvantages

O(n^2) on average and in the worst case for random data.
Many element shifts when the array is in reverse order.

When to use it

Use it for small subarrays (it is the base case inside Quick Sort and Tim Sort) and whenever the data is already close to sorted.