Insertion sort

Small or almost-sorted input? Sort it like a hand of cards. Worked example: insertion sort on 5 2 4 1 3.

The idea

You pick up cards one at a time, and each new card slides left past every bigger card, so the cards in your hand stay sorted. That hand is the sorted part, and it grows by one card each pass.

In the array, picking up the card leaves a gap. Each bigger value to its left shifts one place right, so the gap walks left. When the value on the left is smaller, or the gap reaches the front, the card drops into the gap.

Each shift fixes one pair of values that was out of order. So the work grows with how unsorted the input is:

The walk

Insertion sort on 5 2 4 1 3:

Four passes and 7 shifts in all.

Quick check: insertion sort on 4 3 2 1 makes 6 shifts. The 3 makes 1, the 2 makes 2 and the 1 makes 3.

Pseudocode

function insertionSort(nums):
    for i from 1 to length(nums) - 1:
        card = nums[i]   // pick it up
        j = i - 1
        while j >= 0 and nums[j] > card:
            nums[j + 1] = nums[j]
            j = j - 1
        nums[j + 1] = card   // drop it in
    return nums

The trap: skip line 3 and use nums[i] in lines 5 and 8 instead of a saved card. Line 6 writes over nums[i], so the card is lost: the first shift copies 5 over the 2, and 5 2 4 1 3 comes out as 5 5 5 5 5. With the card saved first, it comes out as 1 2 3 4 5.

Code

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

def insertion_sort(nums):
    for i in range(1, len(nums)):
        card = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > card:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = card
    return nums

#include <vector>
using namespace std;

vector<int> insertionSort(vector<int> nums) {
    for (int i = 1; i < (int)nums.size(); i++) {
        int card = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > card) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = card;
    }
    return nums;
}

function insertionSort(nums) {
    for (let i = 1; i < nums.length; i++) {
        const card = nums[i];
        let j = i - 1;
        while (j >= 0 && nums[j] > card) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = card;
    }
    return nums;
}

Complexity

How it was tested

Insertion sort was run in Java, Python, C++ and JavaScript on 1,210 inputs: 8 hand-picked cases (the empty array, one element, two elements, all equal, sorted, reversed, values at the 32-bit limits, and 5 2 4 1 3), one array of 1,000 random values, and 1,201 random arrays of up to 12 values. Every output matched the language's built-in sort. The pass-by-pass numbers, the shift counts, the quick-check answer and the 5 5 5 5 5 trap result come from running the code.