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

If you are like most candidates, you may think sorting cannot be faster than $O(n log n)$. That is only true for comparison sorts; specialized sorts can be faster when the input has extra structure.

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

Any comparison sort needs $Omega(n log n)$ comparisons. 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.

If the library sort is not stable, add the original index as the final tie-breaker.

4. 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.