Insertion Sort

Given an array of integers, your task is to sort the array in non-decreasing order using the Insertion Sort algorithm.

Insertion Sort builds the final sorted array one element at a time. It is much like sorting playing cards in your hands — you take one card at a time and insert it into its correct position relative to the cards already sorted.

Your goal is to understand how Insertion Sort compares elements, shifts them, and places each item into its correct location during the sorting process.

Understanding the Problem

We are given an array of numbers, and our goal is to sort them in increasing order using a simple technique called Insertion Sort.

Think of how you sort playing cards in your hand. You pick one card at a time and place it in the correct position among the cards you've already sorted. Insertion Sort works just like that — it builds the sorted array one element at a time.

Step-by-Step Solution

We start from the second element (index 1) and compare it with elements before it. If it's smaller than the previous one, we shift the previous one to the right. We keep doing this until we find the right spot for the current element.

We repeat this for every element until the entire array is sorted.

Let’s take an example: [5, 2, 4, 6, 1, 3]

• Start with 2. Compare with 5. Since 2 < 5, shift 5 to the right and place 2 in the first position.
• Now the array becomes: [2, 5, 4, 6, 1, 3]
• Next, take 4. Compare with 5. Since 4 < 5, shift 5 and place 4. Now: [2, 4, 5, 6, 1, 3]
• Next is 6. It's greater than 5, so it stays in place.
• Take 1. It’s smaller than all previous, so shift them all and place 1 at the front: [1, 2, 4, 5, 6, 3]
• Finally, place 3 in its correct spot: [1, 2, 3, 4, 5, 6]

Step by step, we moved each item to its correct position. That’s the core idea!

Edge Cases and Their Intuition

1. Already Sorted Input

Example: [1, 2, 3, 4]
Here, each new element is already in the right position, so no shifting is needed. We only compare. This is the best-case scenario, and it runs very quickly — in linear time.

2. Reverse Sorted Input

Example: [5, 4, 3, 2, 1]
Now, every element must be moved all the way to the front. This takes the most effort — maximum number of comparisons and shifts. This is the worst-case scenario with quadratic time complexity.

3. All Elements Are the Same

Example: [2, 2, 2, 2]
Each element equals the previous one, so no shifting happens. But comparisons are still made. The array remains unchanged, and this case performs better than the worst case.

4. Single Element or Empty Array

Example: [7] or []
These are trivially sorted. The algorithm recognizes this immediately and does nothing. These are special cases and are handled naturally without any extra code.

Finally

Insertion Sort is simple, intuitive, and efficient for small arrays or nearly sorted data. While not optimal for large datasets, it's a great starting point for understanding how sorting works step by step.

1. Start from the second element (index 1) of the array.
2. Set the current element as the key.
3. Compare the key with the elements before it.
4. Shift all elements that are greater than the key one position to the right.
5. Insert the key into its correct position.
6. Repeat the process for all elements until the array is sorted.

Worked example

Let us take the following array and apply the Insertion Sort algorithm to sort the array in ascending order.

Pass 1

Element at index=1 is the key.

Our Goal: Take element 3 at index=1 and insert it into the sorted portion of array.

Shift all elements greater than the key 3, on the left side of the key, one position to the right.

➜ 6 at index=0 is greater than key 3. Move it to right by one position.

Insert key 3 into the correct position index=0.

Pass 2

Element at index=2 is the key.

Our Goal: Take element 8 at index=2 and insert it into the sorted portion of array.

Shift all elements greater than the key 8, on the left side of the key, one position to the right.

Insert key 8 into the correct position index=2.

Pass 3

Element at index=3 is the key.

Our Goal: Take element 2 at index=3 and insert it into the sorted portion of array.

Shift all elements greater than the key 2, on the left side of the key, one position to the right.

➜ 8 at index=2 is greater than key 2. Move it to right by one position.

➜ 6 at index=1 is greater than key 2. Move it to right by one position.

➜ 3 at index=0 is greater than key 2. Move it to right by one position.

Insert key 2 into the correct position index=0.

Pass 4

Element at index=4 is the key.

Our Goal: Take element 7 at index=4 and insert it into the sorted portion of array.

Shift all elements greater than the key 7, on the left side of the key, one position to the right.

➜ 8 at index=3 is greater than key 7. Move it to right by one position.

Insert key 7 into the correct position index=3.

Pass 5

Element at index=5 is the key.

Our Goal: Take element 4 at index=5 and insert it into the sorted portion of array.

Shift all elements greater than the key 4, on the left side of the key, one position to the right.

➜ 8 at index=4 is greater than key 4. Move it to right by one position.

➜ 7 at index=3 is greater than key 4. Move it to right by one position.

➜ 6 at index=2 is greater than key 4. Move it to right by one position.

Insert key 4 into the correct position index=2.

Array is fully sorted.

#include <stdio.h>

void insertionSort(int arr[], int n) {
    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;
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    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;
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array is: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

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
    return arr

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    insertion_sort(arr)
    print("Sorted array is:", arr)

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;
        }
    }
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 4};
        insertionSort(arr);
        System.out.print("Sorted array is: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

function insertionSort(arr) {
    let 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;
    }
}
const arr = [6, 3, 8, 2, 7, 4];
insertionSort(arr);
console.log("Sorted array is:", arr);

package main
import "fmt"

func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

func main() {
    arr := []int{6, 3, 8, 2, 7, 4}
    insertionSort(arr)
    fmt.Println("Sorted array is:", arr)
}

fn insertion_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 1..n {
        let key = arr[i];
        let mut j = i;
        while j > 0 && arr[j - 1] > key {
            arr[j] = arr[j - 1];
            j -= 1;
        }
        arr[j] = key;
    }
}

fn main() {
    let mut arr = [6, 3, 8, 2, 7, 4];
    insertion_sort(&mut arr);
    println!("Sorted array is: {:?}", arr);
}

fun insertionSort(arr: IntArray) {
    for (i in 1 until arr.size) {
        val key = arr[i]
        var j = i - 1
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key
    }
}

fun main() {
    val arr = intArrayOf(6, 3, 8, 2, 7, 4)
    insertionSort(arr)
    println("Sorted array is: " + arr.joinToString(" "))
}

func insertionSort(_ arr: inout [Int]) {
    for i in 1..<arr.count {
        let key = arr[i]
        var j = i - 1
        while j >= 0 && arr[j] > key {
            arr[j + 1] = arr[j]
            j -= 1
        }
        arr[j + 1] = key
    }
}

var arr = [6, 3, 8, 2, 7, 4]
insertionSort(&arr)
print("Sorted array is:", arr)

function insertionSort(arr: number[]): void {
    for (let i = 1; i < arr.length; 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;
    }
}

const arr: number[] = [6, 3, 8, 2, 7, 4];
insertionSort(arr);
console.log("Sorted array is:", arr);

Time complexity

Space complexity

O(1)

Insertion sort is an in-place algorithm. It requires only a constant amount of extra space for the key and index variables, regardless of the input size.