Unit 07
Sorting Techniques
Putting data in order sounds simple, but the method you choose can mean the difference between milliseconds and minutes once the dataset gets large.
// different algorithms reach this same end state at very different speeds
What it is
Sorting rearranges a collection into a defined order, usually ascending or descending. There's no single "best" algorithm — the right choice depends on the data size, whether it's mostly sorted already, and whether you need to sort in place.
Common approaches
- Bubble sort. Repeatedly swaps adjacent out-of-order pairs. Simple to understand, but slow on anything but tiny inputs.
- Selection sort. Repeatedly finds the smallest remaining element and moves it into place.
- Insertion sort. Builds the sorted section one element at a time — fast when the data is already nearly sorted.
- Merge sort. Splits the data in half recursively, sorts each half, then merges them — consistently fast, and stable.
- Quick sort. Picks a "pivot" and partitions data around it — usually very fast in practice, though it has a slow worst case.
Where the simple ones struggle
- Bubble, selection, and insertion sort all take O(n²) time in the worst case, which becomes impractical once data grows into the thousands or millions.
- Quick sort's worst case (O(n²)) can show up with poorly chosen pivots, though good implementations guard against this.
Time complexity
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) |
| Insertion sort | O(n) | O(n²) | O(n²) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) |