Insertion Sort

Easy10–15 min

Topics

SortingArray

Companies

AmazonMicrosoft

Given an array of integers, sort it in non-decreasing order using **Insertion Sort** — build up a sorted prefix one element at a time, inserting each new element into its correct position within that prefix. Insertion sort mirrors how most people sort a hand of playing cards: cards already in hand stay in order, and each new card drawn gets slotted into the right spot among them. It's not the fastest general-purpose sort, but on nearly-sorted data it does very little work, and it needs no extra memory.

Test Case 1:

Input:arr = [7, 2, 9, 4, 2, 8]

Output:[2, 2, 4, 7, 8, 9]

Explanation:A typical unsorted array with a repeated value.

Test Case 2:

Input:arr = []

Output:[]

Explanation:An empty array is already sorted.

Test Case 3:

Input:arr = [5]

Output:[5]

Explanation:A single element is already sorted.

Constraints

◆0 ≤ arr.length ≤ 200
◆-1000 ≤ arr[i] ≤ 1000
◆Sort in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Adjacent Swaps

Good

Grow a sorted prefix one element at a time. For each new element, repeatedly swap it one step to the left with its neighbor as long as it's smaller — the same three-assignment swap used everywhere else, just walked backward until the element lands in the right spot. Correct, but every step of the walk costs a full swap (three writes) even though only one value is actually moving.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int[] insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }
        return arr;
    }
}

Optimal — Shift and Insert

Optimal

Same growing-sorted-prefix idea, but skip the wasted work. Save the new element as key once, then shift every larger element in the sorted prefix one step right (a single write each, not a three-write swap) to open a gap, and drop key into that gap at the end. Same worst-case time as the swap version, but noticeably fewer writes in practice — this is the insertion sort taught in every algorithms course.