Sorting

Sorting often turns complex problems into simpler sweeps.

COMPARISON SORTS VS SPECIALIZED SORTS

If you're like most candidates, you might be under the impression that sorting cannot be done in better than $O(n log n)$ time. That's partially true. To address this confusion, it helps to classify sorting algorithms as comparison sorts and specialized sorts.

COMPARISON SORTS

When asked what's an efficient sorting algorithm, most engineers think of merge sort or quicksort. These are examples of comparison sorts.

Comparison sorts are "one-size-fits-all" algorithms: they can sort any type of data (even user-defined types) based on any sorting criterion. They do it by abstracting the logic of "what goes before what" into a comparator function—a mini-function that takes two elements and determines which one should go first.

Key Idea: Comparison sorts that achieve this asymptotically optimal runtime include merge sort, quicksort, and heapsort. This is why most programming languages leverage one of these algorithms for their built-in sorts.

Merge Sort

Merge sort is a recursive algorithm: it splits the input array down the middle, sorts each half recursively, and then merges the two halves into a single sorted list.

• Time: $O(n log n)$ always.
• Space: $O(n)$ (not in-place).

Quicksort

Quicksort is also recursive: it picks a random element in the array as a pivot and partitions the array into two halves: elements smaller than the pivot and elements larger than the pivot.

• Time: $O(n log n)$ average, $O(n^2)$ worst case.
• Space: $O(log n)$ (stack space).

SPECIALIZED SORTS

Specialized sorts are based on the idea of leveraging the input range. Instead of abstracting out the comparison logic, they are designed with specific types of inputs in mind and take advantage of special properties in those types.

Counting Sort

Sorting n integers in increasing order with a comparison sort takes $O(n log n)$ time. Counting sort is an alternative that takes $O(n + R)$ time and space, where R is the size of the input range. We should only use it when R is small relative to $O(n log n)$, which requires prior knowledge about what the integers represent.

ANALYSIS

Comparison sorts have a proven lower bound: any comparison sort requires at least $O(n log n)$ comparisons to sort n elements.

However, when sorting complex types (like strings), comparison time T isn't constant. For instance, comparing two strings of length k takes $O(k)$ time, so sorting n strings with maximum length K takes $O(K cdot n log n)$. It is a common mistake to forget this!

If you are looking for a linear-time solution, you can't use built-in sorts (or comparison sorts in general), which leaves you two options:

1. Look for a non-sorting solution.
2. Try to apply a specialized sort like counting sort.

CONCEPTS

IN-PLACE SORTING

Like Python's sort(), 'in-place' algorithms mutate the input directly rather than returning a new variable. You should check how to do in-place and not-in-place sorting in your language (like Python's sort() and sorted()), as both can be useful.

The term "in-place" is strongly associated with algorithms that use $O(1)$ extra space, but that is not always the case. Most in-place sorting algorithms, like Python's built-in sort(), still take $O(n)$ extra space. If the rest of your code takes sublinear extra space, the built-in sort could be the space bottleneck.

STABLE SORTING

As mentioned in the custom comparator problem set, a sorting algorithm is considered stable if it preserves the original order of equal elements. For example, imagine you're sorting Person objects based on their age; two different objects might have equal age. If Bob and Alice are both 47 years old, and Bob was before Alice in the original array, should Bob still be before Alice in the sorted array?

Most of the time, it doesn't matter if a sorting algorithm is stable or not. It only matters when the elements you are sorting have fields that you are not sorting on and you care about how you break ties. Perhaps the most common usage in interviews is when a problem says that you should break ties based on the original order in the input.

While most sorting algorithms are not stable by default, most language libraries provide stable sorts. Look into the details of your own language.

KEY TAKEAWAYS

We saw a mix of comparison and specialized sorts:

Algorithm	Time	Space	Type	Stable?
Merge sort	$O(n log n)$	$O(n)$	Comparison sort	✅ Yes
Quicksort	$O(n log n)$	$O(n)$	Comparison sort	❌ No
Counting sort	$O(n + R)$	$O(n + R)$	Integer sort	✅ Yes
Bucket sort	$O(n + R)$	$O(n + R)$	Integer sort	✅ Yes
Quickselect	$O(n)$	$O(n)$	k-th smallest	❌ No

Table 1. Algorithms and their runtimes, where n is the number of elements, and R is the size of the range of integers.

We also learned the concepts you need to speak fluently about sorting: comparison vs specialized sorts, in-place sorting, and stable sorting.

Our main practical advice is to be ready to use the built-in sort during interviews. We emphasized the use of custom comparators to sort any type of data according to any criteria.