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) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
} def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key void insertionSort(vector<int>& arr) {
  for (int i = 1; i < arr.size(); i++) {
    int key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
} void InsertionSort(int[] arr) {
  for (int i = 1; i < arr.Length; i++) {
    int key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
} void insertionSort(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    int key = arr[i], j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
} 

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.