---
title: "Elementary sorts (selection, bubble, insertion)"
url: https://algopath.pro/patterns/elementary-sort
language: en
summary: "Selection, bubble and insertion sort all compare neighbours and swap them. All three cost O(n squared) on a shuffled array."
updated: 2026-08-24
---

# Elementary sorts (selection, bubble, insertion)

Selection, bubble and insertion sort all compare neighbours and swap them. All three cost O(n squared) on a shuffled array.

## How does Elementary sorts (selection, bubble, insertion) work?

All three keep a sorted part and an unsorted part. Each round moves one element across the line.

Selection sort scans the unsorted part for the smallest value. It swaps that value into place.

Bubble sort compares neighbouring pairs and swaps them when they are out of order. The largest value drifts to the end.

Insertion sort takes the next element and slides it left. It stops as soon as the neighbour is smaller.

Insertion sort is the one worth knowing. On nearly sorted data it does almost no work.

All three sort in place with O(1) memory. Insertion and bubble are stable, selection is not.

- `[5 | 2, 4, 1]` Insertion sort. The sorted part is the first element alone.
- `[2, 5 | 4, 1]` 2 slides past 5. Two elements are now in order.
- `[2, 4, 5 | 1]` 4 slides past 5 and stops at 2.
- `[1, 2, 4, 5]` 1 slides all the way to the front. That is the worst move here.
- `3 rounds` Nearly sorted input costs one comparison per element. No sliding happens at all.

## When should you use Elementary sorts (selection, bubble, insertion)?

- n is small (tens or a few hundred)
- array is nearly sorted already
- sort in place with O(1) extra space
- teaching/interview question about how sorting works
- stability matters and simplicity is fine

## What is Elementary sorts (selection, bubble, insertion) confused with?

- **Fast sort (merge / quick)** - Merge and quick sort split the array and cost n log n. These three never split anything.
- **Non-comparison sort (counting / radix)** - Counting sort reads the values instead of comparing them. That needs a small range of keys.
- **Sort with a custom comparator** - That page is about which order you want. This one is about how the order is produced.
- **Binary heap / priority queue** - Selection sort scans for the smallest value every round. A heap hands it over in log n.

## What is the time and space complexity of Elementary sorts (selection, bubble, insertion)?

n up to roughly 5000 is fine at O(n squared). Insertion sort drops to O(n) on nearly sorted data.

## A worked example of Elementary sorts (selection, bubble, insertion)

### Insertion sort on a linked list

You get a singly linked list and have to sort it with insertion sort.

Relinking the nodes is allowed. Copying the values into an array is not.

Build a second, sorted list one node at a time.

For each node, walk the sorted list from the front. Stop once the next value is larger and link it in.

```javascript
function insertionSortList(head) {
    const dummy = new ListNode(0);
    let node = head;

    while (node) {
        const next = node.next;

        // walk from the front each time: the sorted part has no back links
        let prev = dummy;
        while (prev.next && prev.next.val < node.val) {
            prev = prev.next;
        }

        node.next = prev.next;
        prev.next = node;
        node = next;
    }

    return dummy.next;
}
```

## Common mistakes with Elementary sorts (selection, bubble, insertion)

- **Reaching for bubble sort by default** It does the most work of the three for the same cost class. Insertion sort is the better default.
- **Sorting a large input this way** At n of 1e5 the square is 1e10 operations. Call the built-in sort instead.
- **Scanning the inner loop to index zero** Insertion sort should stop once the left neighbour is smaller. Scanning further throws away its best case.
- **Using selection sort where ties matter** A long swap can jump equal keys over each other. Insertion sort keeps their original order.

## Which interview problems use Elementary sorts (selection, bubble, insertion)?

- **Sort an array** Any of the three is enough below a few thousand elements.
- **Insertion sort list** The same loop, over linked nodes instead of slots.
- **Sort colors** Three values only, so one pass beats any comparison sort.
- **Sort a nearly sorted array** Insertion sort is linear when each element is close to home.
- **Height checker** Compare the row against a sorted copy of itself.
- **Sort array by parity** A partition rather than a full sort.
- **First missing positive** Cycle sort puts each value at its own index.

## JavaScript

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

## Python

```python
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
```

## PHP

```php
function insertionSort(array $arr): array {
    for ($i = 1; $i < count($arr); $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}
```