# Sorting Basics — Bubble, Selection and Insertion Sort

Source: https://skills101.in/learn/dsa/dsa-sorting-basics — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

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](https://skills101.in/learn-img/dsa/bubble-passes.svg)

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.

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

```text
[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.

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

```text
[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](https://skills101.in/learn-img/dsa/insertion-steps.svg)

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

```text
[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

```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));
    }
}
```

```text
[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](https://skills101.in/learn-img/dsa/sort-compare.svg)

- 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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-sorting-basics