Skills101

AdvancedData Structures & Algorithms · Lesson 16 of 20 · Updated ·

Sorting Basics — Bubble, Selection and Insertion Sort

Sorting means putting items in order — marks from highest to lowest, names A to Z. Real programs use the built-in sort, but interviews ask you to write a sort and to explain how it behaves. Three simple algorithms come up again and again: bubble, selection and insertion sort. All three take O(n²) time, but they behave differently, and the differences are what interviewers test.

1. Bubble sort: swap neighbours that are in the wrong order

Walk through the array and compare each pair of neighbours. If the left one is bigger, swap them. After one full pass, the largest value has "bubbled" to the end. Repeat for the rest of the array.

Bubble sort on 5 1 4 2 8: pass 1 gives 1 4 2 5 8 with 8 fixed, pass 2 gives 1 2 4 5 8 with 5 and 8 fixed, pass 3 makes no swap so the sort stops early

The useful trick: if a whole pass makes no swap, the array is already sorted and you can stop. That makes bubble sort O(n) on an array that is already sorted.

def bubble_sort(a):
    n = len(a)
    for p in range(n - 1):
        swapped = False
        for i in range(n - 1 - p):          # the last p items are already in place
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a

print(bubble_sort([5, 1, 4, 2, 8]))
print(bubble_sort([3, 3, 1]))
[1, 2, 4, 5, 8]
[1, 3, 3]

2. Selection sort: pick the smallest, put it in front

For each position i, find the smallest value in the unsorted part and swap it into position i. It always does the same number of comparisons, so it is O(n²) even on sorted input. Its one strength: it makes at most n − 1 swaps, which matters only when writing to memory is very expensive.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for k in range(i + 1, n):
            if a[k] < a[m]:
                m = k
        a[i], a[m] = a[m], a[i]
    return a

print(selection_sort([29, 10, 14, 37, 13]))
[10, 13, 14, 29, 37]

Selection sort is not stable: the long-distance swap can jump an item over an equal one. (Stability is explained in the counting sort lesson; in short, a stable sort never changes the order of equal items.)

3. Insertion sort: like sorting cards in your hand

Keep the left part sorted. Take the next item (the "key"), shift every bigger item one step right, and drop the key into the gap.

Insertion sort on 7 3 5 1: insert 3 gives 3 7 5 1, insert 5 gives 3 5 7 1, insert 1 gives 1 3 5 7; the sorted part on the left grows by one each step

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        k = i - 1
        while k >= 0 and a[k] > key:   # shift bigger items right
            a[k + 1] = a[k]
            k -= 1
        a[k + 1] = key
    return a

print(insertion_sort([7, 3, 5, 1]))
print(insertion_sort([1, 2, 3, 5, 4]))
[1, 3, 5, 7]
[1, 2, 3, 4, 5]

On a nearly sorted array the inner while loop stops almost at once, so insertion sort runs in close to O(n). That is why real libraries use insertion sort for small pieces: Python's built-in sort (Timsort) and Java's sort for objects both switch to insertion sort on short runs.

The same in Java

import java.util.Arrays;

public class Main {
    static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], k = i - 1;
            while (k >= 0 && a[k] > key) {
                a[k + 1] = a[k];
                k--;
            }
            a[k + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] a = {7, 3, 5, 1};
        insertionSort(a);
        System.out.println(Arrays.toString(a));
    }
}
[1, 3, 5, 7]

4. Compare them

Table: bubble sort best O(n), worst O(n squared), stable; selection sort always O(n squared), not stable; insertion sort best O(n), worst O(n squared), stable; all use O(1) extra space

  • All three sort in place: O(1) extra memory.
  • For 10⁵ items, n² is 10¹⁰ steps — far too slow. Use an O(n log n) sort (next lesson) or the built-in sort.
  • In an interview, if you're allowed to, just call sorted() / Arrays.sort() and say its complexity: O(n log n).

5. Interview questions about simple sorts

  • "Which sort is best for an almost sorted array?" Insertion sort — close to O(n).
  • "Which is stable?" Bubble and insertion. Selection is not.
  • "Which makes the fewest swaps?" Selection sort: at most n − 1.
  • "How do you sort in descending order?" Flip the comparison (a[k] < key in insertion sort).

Common mistakes

  • Running the inner loop of bubble sort to n − 1 every time instead of n − 1 − p — correct, but wasted work.
  • In insertion sort, writing a[k] >= key in the while — it still sorts, but moves equal items past each other, so the sort is no longer stable.
  • Forgetting the swapped check, which makes bubble sort O(n²) even on sorted input.

Quick recap

  • Bubble: swap neighbours; stop early when a pass makes no swap.
  • Selection: pick the minimum each round; few swaps, not stable, always O(n²).
  • Insertion: insert each item into the sorted left part; stable and fast on nearly sorted data.
  • All three are O(n²) in the worst case and use O(1) extra space.

Practice what you learned

📝 Quiz: Sorting Basics5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →