Sorting Strategies

Why Sort?

Sorting arranges data into order, making searching, grouping, and deduplication trivial.

• Bubble sort: swaps adjacent out-of-order elements.
• Selection sort: finds the smallest remaining element.
• Insertion sort: builds a sorted prefix, inserting new elements. Fast on nearly-sorted or small inputs.

Efficient Sorts & Stability

• Merge sort: divides list in half, recurses, and merges sorted halves. Always $O(n \log n)$ and stable.
• Quicksort: partitions around a pivot ($O(n \log n)$ average, $O(n^2)$ worst case).
• Heapsort: extracts from a heap ($O(n \log n)$ guaranteed).

Stability preserves the relative order of equal elements. Merge sort is stable; Quicksort usually is not.

Pitfall: $O(n \log n)$ is the comparison lower bound ($\Omega(n \log n)$). However, Insertion sort can beat efficient sorts on small inputs due to low overhead.