Designing a High‑Performance Sorting Function: Algorithms and Optimizations

1. Choosing the Right Sorting Algorithm

Linear‑time sorting algorithms have low complexity but are only suitable for special cases; general‑purpose sorting functions cannot rely on them. For small data sets, O(n²) algorithms may be acceptable, while for large data sets O(n·log n) algorithms are far more efficient.

Small‑scale data: consider O(n²) algorithms.

Large‑scale data: prefer O(n·log n) algorithms such as heap sort or quicksort.

To handle any data size, the common choice is an O(n·log n) algorithm. Both heap sort and quicksort are widely used; the JDK uses heap sort for its sort implementation, while C libraries often use quicksort.

2. Merge Sort Analysis

Merge sort is rarely used in practice despite its stable O(n·log n) worst‑case complexity because it is not an in‑place algorithm and requires O(n) additional memory. Sorting 100 MB of data would double the memory consumption, which is often unacceptable.

Quicksort, although having a worst‑case O(n²) complexity, is usually preferred for its in‑place nature and average‑case performance.

3. Optimizing Quicksort

When the input is already sorted or nearly sorted, choosing the last element as the pivot leads to the worst‑case O(n²) behavior. Better pivot selection strategies include:

3.1 Median‑of‑Three

Select the first, middle, and last elements of the current sub‑array, compare them, and use the median value as the pivot. This balances the partitions more evenly.

3.2 Random Pivot

Pick a random element from the sub‑array as the pivot. While it cannot guarantee an optimal split each time, the probability of repeatedly choosing a poor pivot is low, keeping the average performance close to O(n·log n).

Recursive quicksort can cause stack overflow for deep recursion. Two common mitigations are:

Limit recursion depth and switch to a non‑recursive method once a threshold is reached.

Simulate the call stack on the heap, manually pushing and popping frames to avoid system stack limits.

4. Summary

Implementations such as glibc's qsort() may appear to be based on quicksort, but they actually combine multiple strategies: merge sort for small inputs (due to its O(n) extra space), quicksort for larger inputs, and insertion sort for very small partitions (≤ 4 elements) where O(n²) overhead is negligible.

The choice of pivot in qsort() typically follows the median‑of‑three method. Recursive depth is controlled either by limiting recursion or by using an explicit stack on the heap.

Complexity analysis provides theoretical growth trends, but real‑world performance also depends on constant factors. For example, with n = 100 and k = 1000, the expression k·n·log₁₀n + c evaluates to 10 000, which equals n², showing that O(n²) may not always be slower for very small data sets.

Sentinel values can further improve execution efficiency in insertion sort phases of qsort(), reducing unnecessary comparisons.

knlogn+c = 1000 * 100 * log10(0) + 200 >> 10000
n^2 = 100 * 100 = 10000