Insertion Sort — VizionX (CTC)

Insertion Sort is a simple and intuitive sorting algorithm. It builds the sorted array one item at a time by repeatedly taking the next element and inserting it into its correct position among the previously sorted elements.

Insertion Sort is efficient for small or nearly sorted datasets, and it is adaptive: its performance improves when the input is already partially sorted. It is also stable and in-place, requiring only a constant amount of extra memory.

However, for large or random datasets, Insertion Sort is less efficient than more advanced algorithms like QuickSort or Merge Sort.

Time Complexity

Case	Time Complexity
Best (already sorted)	O(n)
Average	O(n²)
Worst	O(n²)

Code Examples

Choose Language:

# Python - insertion sort
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

// C++ - insertion sort
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Java - insertion sort
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

// JavaScript - insertion sort
function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}