Kirkpatrick–Reisch Sort

Kirkpatrick–Reisch sort is a deterministic divide-and-conquer integer sorting algorithm in computation and algorithms introduced by Canadian computer scientist David G. Kirkpatrick and German mathematician Stefan Reisch in 1984. Operating on a random access machine (Word RAM) with word length w = log₂ U bits—where input keys belong to the bounded universe {0, 1, …, U − 1} = {0, 1, …, 2^w − 1}—the algorithm recursively halves the bit length of the sorting problem at linear O(n) cost per recursion level, achieving an upper bound of O(n log(w / log n)) = O(n log(log U / log n)) worst-case time.

Whereas comparison-based sorting algorithms are subject to the information-theoretic lower bound of Ω(n log n) comparisons in computational complexity theory, and least-significant-digit radix sort with base n requires O(n · w / log n) time by processing log n bits per pass, Kirkpatrick–Reisch sort applies the universe-halving philosophy of the van Emde Boas tree to batch integer sorting. When the word size satisfies w = poly(log n) (meaning U = 2^{(log n)O(1)}), the algorithm sorts n integers in O(n log log n) time, exponentially faster than multi-pass radix sort with respect to the ratio w / log n.

Comparison Lower Bounds versus Word RAM Bit Manipulation

In the algebraic comparison tree model, an algorithm gains at most one bit of ordering information from each pairwise comparison x_i < x_j. Because n distinct elements admit n! permutations, any comparison sort requires at least ⌈log₂(n!)⌉ = n log₂ n − O(n) comparisons in the worst and average cases, matching balanced search trees such as red–black trees, AVL trees, splay trees, treaps, and skip lists.

On a Word RAM with integer registers of width w = log₂ U bits, a processor instruction can use an integer key x as a direct memory address or extract its upper and lower bit fields in O(1) time via bit shifts and masks. Two non-comparison techniques define the baseline regimes against which Kirkpatrick–Reisch sort is measured:

1. Direct Bucket Sort and Radix Sort: Counting sort orders n integers in [0, U − 1] in O(n + U) time and space. Decomposing each w-bit key into d = ⌈w / r⌉ digits of r = ⌊log₂ n⌋ bits (radix B = 2^r ≤ n), radix sort executes d stable linear-time counting-sort passes in O(d(n + B)) = O(n · w / log n) = O(n log_n U) time. When w = O(log n), radix sort runs in linear O(n) time, but as w grows larger than log n, its runtime degrades linearly with w / log n.
2. Van Emde Boas Priority Queue Sorting: Inserting n integers into a van Emde Boas tree and repeatedly extracting the minimum sorts n keys in O(n log log U) = O(n log w) time. Because each element is inserted individually into the recursive cluster hierarchy, van Emde Boas sorting does not improve when n approaches U; even when U = n² (where radix sort takes O(n) time), van Emde Boas sorting still requires O(n log log n) time.

Kirkpatrick and Reisch (1984) unified these two regimes by replacing the additive radix factor w / log n with its logarithm log(w / log n).

High/Low Half-Word Bit Decomposition

Assume that the word size w is a power of two (U = 2^w) and that the input consists of n distinct integers x₁, x₂, …, x_n ∈ {0, 1, …, 2^w − 1} (duplicate keys are linked into equivalence lists during bucket grouping). Each w-bit integer x_i is partitioned into two (w/2)-bit half-words corresponding to radix √U = 2^w/2:

• High half-word (bucket index): x_i,H = ⌊x_i / 2^w/2⌋ ∈ {0, 1, …, √U − 1}
• Low half-word (intra-bucket offset): x_i,L = x_i mod 2^w/2 ∈ {0, 1, …, √U − 1}

By construction, x_i = x_i,H · 2^w/2 + x_i,L, and x_i < x_j if and only if x_i,H < x_j,H or (x_i,H = x_j,H and x_i,L < x_j,L).

The Naive Two-Call Trap versus Single-Pass Representative Folding

A naive strategy would recursively sort the n high halves x_i,H to order the non-empty buckets and separately sort the low halves x_i,L within each bucket. However, making two recursive calls on n elements of (w/2) bits yields T(n, w) = 2 T(n, w/2) + O(n), which resolves to O(n · w)—slower than radix sort.

Kirkpatrick and Reisch eliminated the second recursive call through a combinatorial folding technique that merges the inter-bucket high-half sorting problem and all intra-bucket low-half sorting problems into a single recursive call on n keys of length w/2 bits:

1. Step 1 — High-Half Bucket Grouping in O(n) Time: Using an auxiliary array B[0 .. √U − 1] of bucket headers initialized lazily in O(n) active entries, scan the n input keys and append each element x_i to bucket B[x_i,H]. Let k ≤ n denote the number of non-empty buckets, indexed by their distinct high halves h₁, h₂, …, h_k ∈ {0, …, √U − 1}.
2. Step 2 — Maximum Representative Extraction in O(n) Time: Within each non-empty bucket B[h_r], scan its elements in linear time to identify and remove the maximum element m_r = max(B[h_r]). If |B[h_r]| = 1, removing m_r leaves the bucket empty of remaining elements.
3. Step 3 — Forming the Combined (w/2)-Bit Subproblem of Size n: After removing the k bucket maxima m₁, …, m_k, there remain n − k non-maximal elements across all buckets, each needing to be sorted by its low half x_i,L ∈ {0, …, √U − 1}. Simultaneously, the k extracted maxima have k distinct high halves h₁, …, h_k ∈ {0, …, √U − 1} that need to be sorted to order the k buckets. Because (n − k) + k = n, construct a single multiset S′ of n tuples (key′, bucketID, isRep) with (w/2)-bit keys key′ ∈ {0, …, √U − 1}:
   • For each of the n − k non-maximal elements x_i in bucket h_r, insert (key′ = x_i,L, bucketID = h_r, isRep = false).
   • For each of the k bucket maxima m_r, insert (key′ = h_r, bucketID = h_r, isRep = true).
4. Step 4 — Single Recursive Sort on (w/2)-Bit Keys: Recursively sort the n (w/2)-bit keys key′ in S′.
5. Step 5 — Linear-Time Bucket Reconstruction: Scan the sorted sequence S′ from smallest to largest key′ in O(n) time:
   • Whenever isRep = false, append the corresponding element x_i to its bucket list L[h_r]. Because S′ is ordered by x_i,L, each bucket list L[h_r] receives its non-maximal elements in ascending sorted order, after which its saved maximum m_r is appended at the tail of L[h_r].
   • Whenever isRep = true, append the bucket identifier h_r to the global bucket-order list O. Finally, concatenate the sorted lists L[h_r] in the order of O in O(n) time.

Pure Range Reduction: O(n log w) Time

Each range-reduction phase performs O(n) work while halving the key bit length from w to w/2:

Continuing this recursion down to w = 1 bit requires log₂ w = log₂ log₂ U levels and O(n log w) = O(n log log U) total time, matching a van Emde Boas tree.

Early Termination with Base-n Radix Sort: O(n log(w / log n)) Time

Continuing range reduction down to 1-bit keys is unnecessary once the word size w′ falls within a constant multiple of log₂ n. For any fixed constant c ≥ 2, a c-pass base-n radix sort sorts n integers of bit length w₀ = c ⌊log₂ n⌋ bits (universe U₀ = n^c) in linear O(n) time and O(n) space.

Kirkpatrick–Reisch sort halts its range-reduction recursion as soon as w / 2^j ≤ 2 log₂ n after j halving steps, invoking a 2-pass base-n radix sort on the base-case subproblem. The number of range-reduction levels j is:

With O(n) work at each of the j levels plus O(n) in the base-case radix sort, the total worst-case running time is:

This bound interpolates across all integer-sorting regimes:

• Polynomial universe (U = n^O(1), w = O(log n)): j = O(1) levels, running in linear O(n) time.
• Quasi-polynomial universe (w = (log n)^O(1)): j = O(log log n) levels, running in O(n log log n) time.
• Exponential universe (w = 2^{(log n)O(1)}): j = O(log w) levels, matching van Emde Boas trees and radix heaps.

Direct-Addressed Bucket Tables of Size O(√U)

The primary limitation of deterministic Kirkpatrick–Reisch sort is the memory required by the direct-addressed bucket array B[0 .. 2^w/2 − 1] at the top recursion level. Even when the algorithm uses lazy initialization (recording active indices on a stack so only O(n) entries are touched without zeroing the full table), the virtual address space must still allocate 2^w/2 = √U words.

k-Way Range Reduction for Tunable Space O(U^1/k)

To reduce auxiliary memory without hashing, Kirkpatrick and Reisch generalized the binary (w → w/2) split to a k-way digit decomposition for any integer k ≥ 2. Viewing each w-bit integer in base 2^w/k = U^1/k and iteratively folding bucket maxima across the k digits reduces key length from w to w / k bits in O(k · n) time and O(U^1/k + n) space, yielding O(n · k log_k(w / log n)) total time.

Randomized Hashing and Signature Sort

In 1998, Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman combined Kirkpatrick–Reisch range reduction with universal hashing and word-level parallelism to create signature sort. Replacing the O(√U) bucket table with a linear-space O(n) hash table reduces w-bit keys to shorter hashed signatures. Combined with word-packed sorting of compressed signatures and an exponential search tree to restore ordering, signature sort runs in O(n log log n) expected time and O(n) space for all w ≥ log n, and in linear O(n) time when w ≥ (log n)^2+ε.

Deterministic Han–Thorup Sorting and Priority Queues

Subsequently, Yijie Han (2004) and Yijie Han and Mikkel Thorup (2002) combined deterministic range reduction with bit-packed word-level parallelism to achieve O(n log log n) deterministic time and O(n √(log log n)) randomized time in linear O(n) space. By Thorup's (2007) equivalence between integer sorting and priority queues (using monotone radix heaps and exponential search trees), Kirkpatrick–Reisch range reduction underpins modern sub-logarithmic priority queues.

Why does Kirkpatrick–Reisch sort extract the maximum element from each bucket instead of an arbitrary element?

When the algorithm folds the k bucket representatives (sorted by high half h_r) and the n − k remaining elements (sorted by low half x_i,L) into one recursive call, it must reconstruct each bucket's full sorted list afterward. Because every non-maximal element in bucket B[h_r] is smaller than the bucket's maximum m_r, sorting the non-maximal elements by their low halves orders them correctly, and the saved maximum m_r can be appended in O(1) time at the end of the bucket list without sorting its low half.

When is Kirkpatrick–Reisch sort asymptotically faster than radix sort?

Base-n radix sort takes O(n · w / log n) time, whereas Kirkpatrick–Reisch sort takes O(n log(w / log n)) time. Whenever the word length w grows asymptotically faster than log n (such as w = (log n)²), the ratio w / log n is super-constant, and Kirkpatrick–Reisch sort replaces that factor with its logarithm. When w = O(log n), both algorithms run in O(n) time because Kirkpatrick–Reisch sort directly invokes base-case radix sort.

How does Kirkpatrick–Reisch sort handle duplicate integer keys in the input?

During the bucket-grouping pass, elements that have identical full w-bit values are linked together into an equivalence list attached to a single representative key. Because the low-half values within each bucket are then distinct, the maximum element m_r of each bucket is uniquely defined, and at the end of the recursion each representative key expands its linked list of identical copies in O(n) total time.

1. Kirkpatrick, D., & Reisch, S. (1984). "Upper Bounds for Sorting Integers on Random Access Machines." Theoretical Computer Science, 28(3), 263–276. https://doi.org/10.1016/0304-3975(83)90023-390023-3)
2. Andersson, A., Hagerup, T., Nilsson, S., & Raman, R. (1998). "Sorting in Linear Time?" Journal of Computer and System Sciences, 57(1), 74–93. https://doi.org/10.1006/jcss.1998.1580
3. Han, Y., & Thorup, M. (2002). "Integer Sorting in O(n √(log log n)) Expected Time and Linear Space." Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 135–144. https://doi.org/10.1109/SFCS.2002.1181890
4. Han, Y. (2004). "Deterministic Sorting in O(n log log n) Time and Linear Space." Journal of Algorithms, 50(1), 96–105. https://doi.org/10.1016/j.jalgor.2003.09.001
5. Thorup, M. (2007). "Equivalence between Priority Queues and Sorting." Journal of the ACM, 54(6), Article 28. https://doi.org/10.1145/1314690.1314692