Explain bubble, insertion, and selection sort.

Question

Accepted Answer

These are three simple **O(n²)** comparison sorts. They are slow on large inputs but easy to understand and useful for teaching the mechanics of sorting.

## How each works

- **Bubble sort:** repeatedly swap adjacent out-of-order pairs; large values "bubble" to the end each pass.
- **Selection sort:** find the minimum of the unsorted part and swap it into place.
- **Insertion sort:** grow a sorted prefix by inserting each new element into its correct spot.

## Example (insertion sort)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## Comparison

| Sort | Best | Worst | Stable | In-place |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |

## When to use / pitfalls

Insertion sort is genuinely fast for **small or nearly-sorted** arrays and is used inside hybrid sorts. Avoid all three on large unsorted data — use O(n log n) sorts instead.

## Why it matters

These sorts build intuition for invariants, swaps, and stability before you tackle advanced algorithms.

Insertion sort in particular shows up inside production sorts (like Timsort) for tiny subarrays.

Knowing why they are O(n²) makes the leap to O(n log n) sorts meaningful.

Sort	Best	Worst	Stable	In-place
Bubble	O(n)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	No	Yes
Insertion	O(n)	O(n²)	Yes	Yes