Efficient Sorting: Merge, Quick and Heap Sort

Merge sort, quicksort and heapsort improve on elementary quadratic sorting by organizing work across logarithmic levels or maintaining a logarithmic-height structure. Each can sort n items in O(n log n) under important conditions, but their guarantees and resource use differ. Merge sort offers predictable time and natural stability, quicksort often gives excellent array performance with careful pivot handling and heapsort combines worst-case O(n log n) time with constant auxiliary array storage.

The Comparison-Sorting Bound

A deterministic comparison sort learns order only by asking questions such as whether one key precedes another. Its possible executions can be modeled by a decision tree. Sorting n distinct keys must distinguish among n! possible input orders, so the tree needs at least n! leaves. A binary decision tree of height h has at most 2^h leaves, which gives h ≥ log2(n!) = Ω(n log n).

Thus no comparison sort can guarantee asymptotically fewer than n log n comparisons for arbitrary distinct input. Merge sort and heapsort meet this worst-case bound. The result does not apply unchanged to algorithms that use additional information about keys. Counting sort can run in O(n + k) when integer keys lie in a manageable range of size k, because it indexes counts rather than relying only on pairwise comparisons.

Merge Sort

Merge sort follows divide and conquer:

Divide the range into two approximately equal halves.
Recursively sort each half.
Merge the two sorted halves into one sorted range.

A range of size zero or one is already sorted and forms the base case. The recursive structure has about log2 n levels. At each nontrivial level, merging processes a total of n elements, giving Theta(n log n) time in the best, average and worst cases.

The Merge Operation

To merge sorted ranges of lengths a and b, maintain one index for each range and one output index. Compare the first unconsumed values, copy the smaller to the output and advance its index. When one range is exhausted, copy the remainder of the other. Every item is copied once, so merging takes O(a + b) time.

The invariant is that the output prefix contains the smallest consumed elements in sorted order, while each input index points to the smallest unconsumed item in its range. Since both inputs are sorted, the smaller front item is the smallest item still available anywhere.

For stability, when keys compare equal, take the record from the left range first. The left record appeared earlier in the original sequence and choosing it preserves equal-key order across the divide. Taking from the right first can make an otherwise correct merge unstable.

Conventional array merge sort uses an auxiliary array of O(n) space. An efficient implementation allocates one work array and reuses it across recursive calls rather than allocating a new full-size array at every merge. Recursion adds O(log n) frames, dominated by the work array.

On linked lists, merging can reconnect nodes instead of copying array elements and splitting can use slow and fast references. Merge sort therefore suits linked lists particularly well. It also supports external sorting: sorted runs that fit in memory are written to storage and later merged sequentially, avoiding random access over a data set larger than memory.

Bottom-up merge sort removes recursion. It first treats individual items as sorted runs, merges adjacent runs of width one, then widths two, four, eight and so on. It has the same asymptotic time and auxiliary array needs and can be convenient for iterative systems.

Quicksort

Quicksort selects a pivot and partitions a range so that keys on one side belong before the pivot region and keys on the other side belong after it. It then recursively sorts the resulting subranges. Partitioning takes linear time in the range length, but total performance depends on partition balance.

If every pivot divides the input into roughly equal parts, recursion has O(log n) levels and each level performs O(n) partition work, yielding O(n log n). If the pivot repeatedly produces ranges of sizes zero and n - 1, the work becomes:

n + (n - 1) + ... + 1 = Theta(n²)

Already sorted input can trigger this behavior when the first or last element is always chosen as pivot under a vulnerable scheme.

Partition Schemes

In Lomuto partitioning, a pivot is commonly moved to the end. A boundary separates items known to be no greater than the pivot from unclassified items. After scanning, the pivot is exchanged into its final boundary position and that index is returned. Recursive calls exclude the finalized pivot.

Hoare partitioning commonly uses two indices moving inward. The left index stops on an item belonging on the right and the right stops on an item belonging on the left; those values are exchanged until the indices cross. It returns a boundary between partitions, not necessarily the final index of the selected pivot. The recursive ranges differ from Lomuto’s.

A correct quicksort must match its recursion boundaries to the exact partition contract. Treating a Hoare boundary as a finalized pivot index or including an unchanged range again, can skip values or cause infinite recursion.

Pivot Selection and Equal Keys

Random pivot selection makes the running time O(n log n) in expectation under the randomness model, even for a fixed adversarial input. It does not make quadratic execution impossible. Median-of-three selection uses the first, middle and last values to avoid some predictable extremes, but it is still a heuristic rather than a worst-case guarantee.

Inputs with many equal keys can cause poor two-way partitions. Three-way partitioning divides the range into keys less than, equal to and greater than the pivot. The equal region needs no recursive processing, so an all-equal input can finish in linear partition time rather than creating deep recursion.

Ordinary in-place quicksort is not stable because partition exchanges can move equal records past one another. Its array locality and small constants often make it fast in practice. Expected recursion space is O(log n), but naive worst-case depth is O(n). Recursing on the smaller partition first and iterating over the larger limits active stack depth to O(log n) even when partition sizes are uneven, though running time can still be quadratic.

Heapsort

Heapsort interprets the array as a complete binary tree. For ascending output, it builds a max-heap in which every parent is at least as large as its children. The maximum is then at index zero.

The algorithm repeatedly exchanges the root with the last item in the active heap, decreases the heap size and sifts the replacement root downward. The swapped maximum lies in its final sorted position and is excluded from future heap operations. The invariant is that the active prefix is a valid max-heap and the inactive suffix is sorted and contains the largest keys.

Bottom-up heap construction starts with the last internal node and sifts nodes down toward the root. Although an individual sift can cost O(log n), most nodes are near the leaves and travel little or not at all. Summing work by node height gives O(n) construction time.

There are n - 1 root removals, each costing at most O(log n), so total heapsort time is O(n log n) in best, average and worst cases. The standard array form uses O(1) auxiliary storage. It is not stable because long-distance root exchanges can reverse equal records. Its access pattern is less cache-friendly than quicksort’s, but its time and space guarantees are valuable.

Comparing the Three Algorithms

Merge sort guarantees Theta(n log n) time and is naturally stable with the correct tie rule. Array merging needs O(n) auxiliary storage, but linked and external data benefit from its sequential access.

Quicksort has expected O(n log n) time with good pivot selection and O(n²) worst-case time for ordinary implementations. It is typically in-place apart from recursion and often performs very well on arrays. Three-way partitioning handles duplicate-heavy data and introspective variants switch algorithms if recursion becomes dangerously deep.

Heapsort guarantees O(n log n) time and uses O(1) auxiliary array space. It is not stable and often has larger constant costs and weaker locality than a well-engineered quicksort.

Hybrid library sorts combine strengths. An introsort may begin with quicksort, switch to heapsort when depth exceeds a limit and use insertion sort for small ranges. Stable object sorting may use merge-based techniques that exploit existing ordered runs. Algorithm names alone do not specify every library guarantee, so stability and comparator requirements should be checked in the relevant API.

Correctness and Defensive Implementation

Merge sort correctness follows by induction: recursively sorted halves are combined by a merge that always selects the smallest remaining front value. Quicksort depends on a partition invariant proving that every returned subrange is smaller and placed on the correct side. Heapsort depends on heap order in the active prefix and finalized order in the suffix.

Index arithmetic requires care. Midpoints should avoid overflow by using low + (high - low) / 2. Heap child formulas must be evaluated only when indices lie inside the active heap. Comparator code should not subtract potentially extreme integers because subtraction can overflow.

Tests should include empty and single-item ranges, sorted and reverse order, all equal keys, duplicate tagged records, extreme key values and sizes around partition or merge boundaries. Verify sorted order and preservation of every input record. Stability must be checked using identities attached to equal keys.

The appropriate algorithm follows from required guarantees. Choose merge sort when stability, linked data or sequential external access dominates; quicksort when fast in-memory array sorting and careful engineering are available; and heapsort when constant auxiliary space and worst-case O(n log n) time are central.