Sorting is the single most important preprocessing step in algorithm design. Once data is sorted, problems that would require brute-force O(n^2) comparisons suddenly become solvable with O(n) two-pointer scans or O(log n) binary searches. Before you learn those techniques, you need to understand what sorting gives you and what it costs.

Comparison-Based Sorting

Most sorting algorithms work by comparing pairs of elements and deciding their relative order. The key insight is that any comparison-based sorting algorithm must make at least O(n log n) comparisons in the worst case. This is not a limitation of specific algorithms - it is a mathematical lower bound. No comparison-based sort can beat O(n log n).

The two most important comparison sorts for interviews are merge sort and quicksort.

Merge sort guarantees O(n log n) time in every case. It splits the array in half, recursively sorts each half, and merges the sorted halves. The merge step is the key operation - it combines two sorted arrays into one sorted array in O(n) time. Merge sort is stable (equal elements keep their original order) and works well for linked lists and external sorting. The downside is O(n) extra space for the merge buffer.

Quicksort picks a pivot element, partitions the array so everything smaller goes left and everything larger goes right, then recursively sorts each partition. Average case is O(n log n), but worst case is O(n^2) when the pivot is consistently the smallest or largest element. In practice, randomized pivot selection makes the worst case extremely unlikely, and quicksort is faster than merge sort due to better cache locality and lower constant factors. Most language standard libraries use quicksort (or a hybrid like introsort) as their default sort.

Merge Sort:  Always O(n log n)  |  O(n) space  |  Stable
Quicksort:   Avg O(n log n)     |  O(log n) space  |  Not stable

Non-Comparison Sorting

When your data has special structure, you can sort faster than O(n log n). Non-comparison sorts do not compare elements to each other - they exploit the structure of the keys directly.

Counting sort works when values fall in a known, small range. It counts occurrences of each value, then places elements in order based on those counts. Time complexity is O(n + k) where k is the range of values. If you are sorting exam scores (0-100), counting sort finishes in O(n) time.

Radix sort processes digits one at a time, from least significant to most significant, using a stable sub-sort (usually counting sort) at each digit position. For d-digit numbers in base b, it runs in O(d(n + b)) time. When d is constant (like sorting 32-bit integers), this is effectively O(n).

Stability and When It Matters

A sorting algorithm is stable if elements with equal keys appear in the same order in the output as they did in the input. This matters when you sort by multiple criteria. For example, if you sort a list of students first by name, then by grade using a stable sort, students with the same grade remain alphabetically ordered. An unstable sort would scramble the name order within each grade.

Merge sort and counting sort are stable. Quicksort and heap sort are not. Python's sort() uses Timsort, which is stable. Java's Arrays.sort() uses dual-pivot quicksort for primitives (unstable) and Timsort for objects (stable).

Choosing the Right Sort