Sorting

Sorting arranges data so the next step can use a simple scan, two pointers, binary search, or direct neighbor comparisons.

1. Comparison Sorts vs. Specialized Sorts

The worst-case comparison lower bound is $\Omega(n \log n)$. Specialized sorts can be faster by using a restricted key range or representation.

Comparison sorts

Comparison sorts decide order by repeatedly asking which of two elements comes first. They work for arbitrary data and custom ordering rules.

Specialized sorts

Specialized sorts exploit a restricted input type or range. They are often the best choice in the right context, but cannot be used beyond it.

Counting sort counts each integer value, then rebuilds the output in order. For values in a range of size $R$, it takes $O(n + R)$ time and $O(R)$ space. Use it only when $R$ is small compared with $n \log n$.

If the range starts at min_value instead of zero, map value to index value - min_value.

Analysis

Comparison sorting arbitrary distinct keys needs $\Omega(n \log n)$ comparisons in the worst case. If each comparison costs $T$, sorting costs $O(Tn \log n)$; sorting $n$ strings of maximum length $K$ can therefore cost $O(Kn \log n)$.

Specialized sorts are not subject to that lower bound. If a problem requires linear time, use input constraints to find a specialized method or avoid sorting.

2. Using the Built-in Sort

In interviews, default to the language's built-in sort because it uses less interview time and is less error-prone. Ask the interviewer if the problem specifically requires implementing a sorting algorithm.

Know whether your API mutates the input:

• Python items.sort() mutates the list and returns None.
• Python sorted(items) returns a new list.

Include the built-in sort's usual $O(n \log n)$ cost in the total algorithm.

Custom comparators

Know how to sort ascending, descending, by one field, and with tie-breakers. In Python, a tuple key compares fields from left to right:

ordered = sorted(
    players,
    key=lambda player: (-player.score, player.name),
)

Use a rank map when categories need a custom order. Pairwise comparators must be consistent and transitive.

3. Concepts

In-place sorting

An in-place sorting API mutates the input instead of returning a new collection. This does not automatically mean $O(1)$ extra space; a library sort may mutate the input and still allocate temporary memory.

State input mutation and auxiliary space separately.

Stable sorting

A stable sort preserves the original relative order of elements with equal keys. It matters when ties must follow input order or when unsorted fields still carry meaningful order.

Python's built-ins are stable: both list.sort() and sorted(items) use Timsort, so equal keys already keep their input order without extra tie-breakers. If the library sort is not stable, add the original index as the final tie-breaker.

4. Make the Sorted Order Do Useful Work

For Merge Intervals, sort by start, keep one active interval, and extend its end while the next start overlaps it. Otherwise emit the active interval and start another. Sorted starts guarantee no later interval can bridge a completed gap. The scan is $O(n)$ after sorting; define whether touching endpoints overlap.

When repeated queries remove the current smallest value but the final output must retain input order, sort indices by value and mark deletions separately. Advance through sorted indices, skipping deleted ones; reconstruct in original index order. Across the whole scan, each index is skipped at most once. This is the chapter's reusable alternative to a heap for data known upfront; dynamic arrivals point toward Heaps.

For a single kth-element query, randomized quickselect partitions around a pivot and continues only in the side containing the desired rank. Expected time is $O(n)$, worst case $O(n^2)$; unlike sorting, it does not order the whole array. For repeated ordered queries, paying for a full sort may be simpler.

5. Key Takeaways

• The $O(n \log n)$ lower bound applies to comparison sorts, not specialized sorts.
• Use counting sort only when the numeric range is small enough.
• Default to the built-in sort and know its custom-comparator syntax.
• Include comparison cost, sorting time, mutation, and extra space in the analysis.
• Know whether equal keys must preserve their original order.

Continue to Two Pointers for sorted scans and Binary Search for boundary queries.