Selection, bubble and insertion sort

Every language has a built-in sort, so why learn to write one? Because interviewers ask for it, and because the ideas behind these three sorts come back in many later patterns.

Learners usually mix the three up a week later. So each one gets a one-line picture to remember it by.

Read the problem

Questions to ask before you code:

• Same array or a new one? All three sorts in this lesson work inside the array you are given.
• Repeated values? They must all stay. Equal values can still swap places, unless the sort is stable (more on that below).
• Negative numbers? Nothing changes. The sorts only compare with < and >.
• One item? It is already sorted. The loops run zero times.

With n up to 1,000, an O(n²) sort does about 1,000,000 steps. That fits easily.

We use the same six numbers all chapter, so you can compare every sort on one input.

Three sorts in three lines

Each one grows a sorted part of the array, one item per pass. They differ in which item they move and how.

Selection sort: find the smallest, put it in front

1. Scan the unsorted part and find the smallest value.
2. Swap it with the first unsorted slot.
3. That slot is now final. Repeat on the rest.

JavaPythonTypeScript

int[] selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) min = j;
        }
        if (min != i) {
            int t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
    }
    return a;
}

• i marks the first unsorted slot. Everything before it is sorted and final.
• min holds the index of the smallest value seen so far in this pass. Python calls it min_i, because min is a built-in function there.
• The swap: Python and TypeScript swap two values in one line. Java has no such line, so it parks one value in t first.

Cost. The first pass compares 5 pairs, then 4, 3, 2, 1. That is 15, or n(n − 1) / 2.

The scan never stops early, so even a sorted array costs O(n²). Its one strength: at most n − 1 swaps.

Bubble sort: the biggest bubbles to the end

1. Walk left to right and compare each pair of neighbours.
2. If the left one is bigger, swap them.
3. After one pass, the largest value sits at the end. Repeat on the rest.

JavaPythonTypeScript

int[] bubbleSort(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean swapped = false;
        for (int j = 0; j < end; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return a;
}

• end is the last slot this pass can reach. Everything after it is final.
• swapped is the early exit. A pass with no swaps means every neighbour pair is in order, so the array is sorted.

Cost. The worst case is the same 15 comparisons, O(n²). With the flag, a sorted array takes one pass of 5 comparisons: O(n). Without the flag, it would still do all 15.

Insertion sort: slide each card into place

Think of a hand of playing cards. You pick up one card at a time and slide it left until the card before it is smaller.

1. The first item alone is a sorted hand.
2. Take the next item. While its left neighbour is bigger, swap them.
3. Stop when the left neighbour is smaller or equal. Take the next item.

JavaPythonTypeScript

int[] insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int j = i;
        while (j > 0 && a[j - 1] > a[j]) {
            int t = a[j - 1];
            a[j - 1] = a[j];
            a[j] = t;
            j--;
        }
    }
    return a;
}

• i is the next card to insert. Everything before i is sorted, but not final yet.
• j follows the card as it slides left.

Cost. A reversed array makes every card slide to the front: 15 comparisons, O(n²). A sorted array makes every card stop at once: 5 comparisons, O(n).

Why insertion sort loves nearly sorted data

Each card stops as soon as it meets a smaller one. If most items are already near their place, most cards move zero or one slot. The work is close to n.

Take [9, 13, 24, 20, 46, 52], sorted except for one pair:

That is why real libraries use insertion sort for short or nearly sorted pieces (see the example below).

The recursive versions

Both loops above can be written as recursion. The base case stops it, and each call works on a smaller part, as in the recursion chapter.

JavaPythonTypeScript

int[] bubbleRec(int[] a, int end) {
    if (end <= 0) return a;
    boolean swapped = false;
    for (int j = 0; j < end; j++) {
        if (a[j] > a[j + 1]) {
            int t = a[j];
            a[j] = a[j + 1];
            a[j + 1] = t;
            swapped = true;
        }
    }
    if (!swapped) return a;
    return bubbleRec(a, end - 1);
}

• Bubble: one pass puts the largest at end. Then sort the part before it the same way.
• Base case: one item left (end <= 0), or a pass with no swaps.

JavaPythonTypeScript

int[] insertionRec(int[] a, int i) {
    if (i >= a.length) return a;
    for (int j = i; j > 0 && a[j - 1] > a[j]; j--) {
        int t = a[j - 1];
        a[j - 1] = a[j];
        a[j] = t;
    }
    return insertionRec(a, i + 1);
}

• Insertion: slide card i into the sorted left part, then call again for card i + 1.
• Base case: i has passed the last card.
• The first call: TypeScript fills in end and i by default. Java has no default values, so call bubbleRec(a, a.length - 1) and insertionRec(a, 1). Python needs bubble_rec(a, len(a) - 1).
• Python has no loop with a condition in its header, so its insertion step uses a while loop. The steps are the same.

The time stays O(n²). The call stack adds up to n frames, so extra space grows from O(1) to O(n).

That stack has a limit. In Python, the default limit is 1,000 calls, and insertion_rec on 1,000 items raised RecursionError in a test.

Raise the limit with sys.setrecursionlimit(10_000), or use the loop version. In Java, the same call handled 10,000 items and threw StackOverflowError at 100,000.

Stable or not

Stable matters when you sort records by one field. Here a list sorted by name gets sorted by marks:

┌─────────────────────────────────────────────┐
│                                             │
│   input       Asha 80   Ben 80    Cara 70   │
│                                             │
│   stable      Cara 70   Asha 80   Ben 80    │
│   (insertion)                               │
│                                             │
│   not stable  Cara 70   Ben 80    Asha 80   │
│   (selection)                               │
│                                             │
└─────────────────────────────────────────────┘

Selection sort swaps Asha, at the front, with Cara at the end. That long jump throws Asha behind Ben.

Bubble and insertion sort only swap neighbours, and only when the left one is strictly bigger. Two equal values never pass each other, so both are stable.

Side by side

Counted from a run on [13, 46, 24, 52, 20, 9]:

Bubble and insertion both made 9 swaps. That is no accident: the array has 9 pairs in the wrong order, and each neighbour swap fixes exactly one.

When to use them

• The problem asks you to write a sort and n is small (a few thousand at most).
• The data is nearly sorted: reach for insertion sort.
• Writes are expensive: selection sort makes the fewest swaps.
• n is large: none of them. Use merge sort or quick sort from the next two lessons.

take U forwardYouTube

Read more

• VisuAlgo: sorting, watch each sort run on your own numbers
• Insertion sort on Wikipedia, with its link to nearly sorted data
• Getting things sorted in V8, how a real engine mixes insertion sort with faster sorts
• Array.prototype.sort() on MDN, including what "stable" means for JavaScript

Next: merge sort, the first sort that fits n = 10⁵, built from the recursion you already know.