Bucket Sort

Bucket sort (also called bin sort or distribution sort) is a non-comparison sorting algorithm that runs in O(n) expected time when the input is drawn from a known distribution and is roughly uniform over a known range. The algorithm partitions the n input elements into k “buckets” (sub-arrays) according to a hash-like assignment function — typically bucket_index = floor(k · (x − min) / (max − min)) for numeric data on a bounded range — sorts each bucket independently (usually with Insertion Sort, because each bucket is expected to be small), and concatenates the buckets in order to produce the final sorted output. The key trick is that the bucket-assignment step is O(n) and the concatenation step is O(n + k), so the whole algorithm runs in linear time if and only if the per-bucket sort cost stays low — which it does precisely when the input is uniformly distributed across the bucket range. On adversarial inputs where every element lands in the same bucket, bucket sort degrades to whatever the per-bucket sort is, typically Insertion Sort’s Θ(n²). So bucket sort is a distribution-aware algorithm: brilliant on its niche of “uniform numeric data on a known range” (random floats in [0, 1), sensor readings with known min/max, hash values), useless on data with skewed or unknown distribution. It is the natural cousin of Counting Sort (which works on small-integer ranges) and Radix Sort (which extends bucketing to multiple digit passes for fixed-width keys).

1. Intuition — Sorting the Mail at the Post Office

Imagine a postal sorting facility receiving thousands of letters, each addressed to a house number from 1 to 100. A naïve approach would compare letters pairwise to build a global sorted pile — O(n log n) time. The actual postal approach is dramatically faster: set up 10 bins labeled “1–10”, “11–20”, …, “91–100”, glance at the first two digits of each letter’s house number, and toss it into the matching bin. After the toss-pass — O(n) work — each bin holds only the letters destined for ten consecutive houses, ideally about n / 10 letters per bin. Each bin can then be hand-sorted in roughly constant time per bin (because each bin is small), and finally the bins are stacked end-to-end in label order to produce a sorted output pile. Total work: O(n) for the toss-pass, O(n) total for the per-bin sorts (provided the load is balanced), O(n + k) for the concatenation — O(n) overall.

The whole trick rides on uniform load across bins. If every letter happens to be addressed to house number 7, all n letters land in bin “1–10”, which then needs to be sorted by some general-purpose method — and the speed advantage evaporates. The postal analogy works because real-world mail volumes are roughly uniform across address ranges; bucket sort works because real-world numeric inputs in a known range are often roughly uniform. When the assumption fails — Zipfian distributions, clustered data, adversarial inputs — bucket sort fails proportionally.

2. Tiny Worked Example (n = 8 floats in `[0, 1)`)

Sort [0.42, 0.13, 0.91, 0.27, 0.55, 0.08, 0.71, 0.34] using k = 10 buckets.

Step 1 — Bucket assignment (`O(n)`)

For each x, compute bucket_index = floor(10 · x):

Value `x`	`floor(10x)`	Goes into bucket
0.42	4	B[4]
0.13	1	B[1]
0.91	9	B[9]
0.27	2	B[2]
0.55	5	B[5]
0.08	0	B[0]
0.71	7	B[7]
0.34	3	B[3]

After the assignment pass, the buckets contain:

B[0] = [0.08]
B[1] = [0.13]
B[2] = [0.27]
B[3] = [0.34]
B[4] = [0.42]
B[5] = [0.55]
B[6] = []
B[7] = [0.71]
B[8] = []
B[9] = [0.91]

In this happy case each non-empty bucket holds exactly one element, so the per-bucket sort is trivially O(1).

Step 2 — Sort each bucket (`O(n)` expected)

Each bucket is sorted with Insertion Sort. With at most one element per bucket here, no work is needed; each bucket is already sorted.

Step 3 — Concatenate (`O(n + k)`)

Walk the bucket array B[0..9] in order, appending each bucket’s contents:

[0.08, 0.13, 0.27, 0.34, 0.42, 0.55, 0.71, 0.91]

That is the sorted output. Total work: 8 assignment ops + 0 sorting ops + 10 bucket walks (some empty) = O(n + k) = O(n) since k = O(n).

Skewed Counter-Example

Now consider an adversarial input: [0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08] with the same k = 10 buckets.

B[0] = [0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08]
B[1] = ... = B[9] = []

All n elements land in B[0]. Sorting B[0] with Insertion Sort takes O(n²) = O(64) here — no better than just running insertion sort on the original input. The bucket assignment was wasted work.

This trace exposes the algorithm’s central tension: the assignment step is fast and oblivious to the input distribution, but the sorting step’s cost is fully determined by the input distribution. Uniform input is fast; skewed input is slow.

3. Pseudocode

bucket_sort(arr, k):
    n := length(arr)
    if n <= 1: return arr
    min_val := min(arr); max_val := max(arr)
    range := max_val - min_val
    buckets := array of k empty lists

    # Step 1: assign each element to a bucket (O(n))
    for x in arr:
        if range == 0:                       # all elements equal — trivial
            buckets[0].append(x)
        else:
            idx := floor(k * (x - min_val) / range)
            if idx == k: idx := k - 1        # clamp the max-value edge case
            buckets[idx].append(x)

    # Step 2: sort each bucket (expected O(n) total for uniform data)
    for i in 0..k-1:
        insertion_sort(buckets[i])

    # Step 3: concatenate buckets in order (O(n + k))
    result := empty list
    for i in 0..k-1:
        result.extend(buckets[i])
    return result

A few subtleties worth narrating:

The if idx == k: idx := k - 1 clamp handles the corner case where x == max_val produces idx = k (out of bounds for an array of size k). An equivalent fix is to compute idx = floor(k * (x - min_val) / (range + epsilon)). Either approach must be in the implementation; forgetting it is a common bug.
range == 0 means all input elements are equal — the algorithm reduces to placing them all in buckets[0]. Without this guard the division becomes 0 / 0.
The choice of k (number of buckets) is a tuning parameter. CLRS recommends k = n for O(n) expected time on uniform data; smaller k increases per-bucket size and per-bucket sort cost; larger k increases the O(k) concatenation cost. k = n is the sweet spot when data is uniform; for non-uniform distributions, k can be tuned differently.

4. Python Implementation

def bucket_sort(arr: list[float], k: int = None) -> list[float]:
    """Bucket sort for numeric data on a bounded range.
    Stable: depends on per-bucket sort (yes if insertion sort is used).
    Adaptive: somewhat — already-sorted buckets are O(n) to sort."""
    n = len(arr)
    if n <= 1:
        return arr[:]
    if k is None:
        k = n                                    # CLRS default
    lo, hi = min(arr), max(arr)
    if lo == hi:
        return arr[:]                            # all equal — already sorted
 
    # Step 1: distribute into k buckets
    buckets: list[list[float]] = [[] for _ in range(k)]
    width = hi - lo
    for x in arr:
        idx = int(k * (x - lo) / width)
        if idx == k:
            idx = k - 1                          # clamp the max-value edge case
        buckets[idx].append(x)
 
    # Step 2: sort each bucket with insertion sort
    for bucket in buckets:
        _insertion_sort(bucket)
 
    # Step 3: concatenate
    result = []
    for bucket in buckets:
        result.extend(bucket)
    return result
 
 
def _insertion_sort(arr: list[float]) -> None:
    for i in range(1, len(arr)):
        x = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > x:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = x

Two implementation choices to call out. First, the per-bucket sort is _insertion_sort, not Python’s built-in list.sort() — using list.sort() would still give a correct algorithm but defeats the analytical claim of O(n) expected time, because list.sort() is O(n log n). The reason insertion sort is the canonical choice is that on the expected per-bucket size of O(1) (for uniform data, k = n, expected size is exactly 1), the constant factor of insertion sort is the smallest among comparison sorts. Second, the implementation returns a new list rather than sorting in place, which simplifies the bucket-assignment step but doubles the auxiliary memory; an in-place variant exists but is awkward.

5. Complexity Analysis

5.1 Time

Average / Expected case (uniform input on [lo, hi), k = n):

The crucial calculation is the expected total cost of the per-bucket sorting step. Let n_i denote the (random) number of elements falling into bucket i. Since each element lands in each bucket with probability 1 / k = 1 / n, the variable n_i is binomial with parameters n and 1 / n, giving:

E[n_i]   = n · (1 / n) = 1
E[n_i²]  = Var[n_i] + (E[n_i])²
         = n · (1 / n) · (1 − 1 / n) + 1
         = 2 − 1 / n
         < 2

where:

n_i is the number of input elements assigned to bucket i.
E[·] denotes expected value over the randomness in the input distribution.
Var[n_i] is the variance of n_i, which for a binomial(n, p) random variable equals np(1 − p).
The last inequality uses 1 / n < 1 to drop the −1 / n term.

The cost of insertion-sorting bucket i is O(n_i²) in the worst case. The total expected per-bucket sort cost is:

E[Σ_i O(n_i²)] = Σ_i E[O(n_i²)] = O(Σ_i E[n_i²]) = O(k · 2) = O(k) = O(n)

where the last step uses k = n. Adding the O(n) assignment cost and the O(n + k) = O(n) concatenation cost: total expected time is O(n). This is the famous O(n) expected bound for bucket sort on uniform data, derived in CLRS Theorem 8.4.

Worst case: all n elements land in a single bucket. The per-bucket sort then takes O(n²) (insertion sort on n elements). Total worst-case time: O(n²). This is the cost of the algorithm’s distributional assumption — when the assumption fails, the algorithm falls back to insertion sort’s worst case.

Best case: each bucket gets at most one element, per-bucket sort is O(1) per bucket, total O(n + k) = O(n). Same as the average case.

5.2 Space

Auxiliary space is O(n + k): the k bucket headers plus the total of n elements distributed across them. With k = n (the standard choice), this is O(n). Bucket sort is not in-place in its standard auxiliary-bucket formulation — the textbook algorithm allocates an explicit array of k lists (CLRS 8.4 introduces B[0..n-1] as an auxiliary array of n linked lists), and elements are moved into the auxiliary structure before being written back. A histogram-sort style in-place variant exists (count first, then permute in place using cycle leaders), but it is far more intricate to implement correctly and loses the conceptual simplicity that makes bucket sort attractive in the first place (Wikipedia: Bucket sort — Histogram sort). When practitioners say “bucket sort,” they almost always mean the auxiliary-bucket model — O(n + k) extra memory is part of the price.

5.3 Why the `O(n)` Bound Sidesteps the Comparison-Sort Lower Bound

The Ω(n log n) lower bound for sorting only applies to comparison-based sorts — algorithms that learn information about the input only through pairwise comparisons. Bucket sort uses a different information source: the bucket-assignment function reads the value of each element directly (not just compares it), and uses that value to compute a numeric bucket index. This is a distribution-aware primitive: it requires that elements come from a known totally ordered numeric range and that the algorithm knows (or can compute in O(n)) the range bounds.

The escape from Ω(n log n) is therefore the same trick used by Counting Sort and Radix Sort: trade generality (works on any totally-ordered data with comparisons) for additional input assumptions (knowledge of the numeric range or representation), in exchange for breaking the lower bound. Bucket sort is the most permissive of the three — it accepts any numeric data on a bounded range — but pays the price of vulnerability to non-uniform distributions.

6. Comparison with Counting Sort and Radix Sort

These three are the canonical “non-comparison” sorts. Their distinguishing characteristics:

Algorithm	Input requirement	Time	Space	Stable	When to use
Bucket Sort	numeric data on bounded continuous range, roughly uniform	`O(n)` expected, `O(n²)` worst	`O(n + k)`	Yes (with stable per-bucket sort)	Uniform floats in `[0, 1)`, sensor data with known bounds
Counting Sort	small-integer keys in range `[0, K]`	`O(n + K)`	`O(n + K)`	Yes	Discrete keys with small `K`, e.g., grades 0–100
Radix Sort	fixed-width integer / string keys	`O(d · (n + K))` for `d` digits	`O(n + K)`	Yes (LSD variant)	Large-integer keys, fixed-length strings

The relationship between the three is illuminating: counting sort is bucket sort with k = K + 1 and one element per bucket category (no per-bucket sort needed because all elements in a bucket are equal). Radix sort is repeated counting sort across digit positions, exploiting the structure of fixed-width numeric or string keys. Bucket sort generalizes to continuous numeric data by allowing buckets to contain multiple elements that need further sorting.

The choice between them in practice:

If your keys are small non-negative integers (e.g., test scores, ages, RGB color components), use counting sort. The K (range size) is small, the O(n + K) time is genuinely linear, and there is no distributional assumption.
If your keys are fixed-width (32-bit ints, 8-character strings) and you can pay the digit-iteration overhead, use radix sort. It works regardless of distribution.
If your keys are continuous numeric values on a known range with roughly uniform distribution, use bucket sort. The O(n) expected time wins, but profile your data first to confirm uniformity.
If your distribution is unknown or skewed, fall back to a comparison sort like Quicksort or Tim Sort — bucket sort’s worst-case O(n²) will bite you on adversarial input.

7. Stability and Adaptiveness

Stable: Conditionally yes. Bucket sort is stable if and only if the per-bucket sort is stable and the bucket assignment is order-preserving for elements that map to the same bucket. The standard implementation using Insertion Sort for per-bucket sorting is stable, and the assignment step using floor(k · (x − min) / range) is deterministic and order-preserving (elements appended to a bucket in input order remain in input order). So bucket sort with insertion-sort sub-sorting is stable.

If a faster but unstable per-bucket sort is used (e.g., quicksort), the overall algorithm is unstable. This is a relevant choice if buckets occasionally get large: insertion sort’s O(n²) per-bucket cost might be worse than quicksort’s O(n log n) for large unbalanced buckets, but the trade-off is loss of stability.

Adaptive: Partial. The per-bucket Insertion Sort is adaptive — already-sorted buckets are processed in O(n) total. So bucket sort on already-sorted input runs in O(n) time (assignment + adaptive insertion-sort + concatenation). However, bucket sort does not detect already-sorted input distributions and skip the bucket-assignment step the way Tim Sort detects sorted runs.

8. Variants

8.1 Generalized (Non-Uniform) Bucketing

For known but non-uniform distributions, the bucket boundaries can be chosen non-uniformly to equalize expected bucket sizes. For example, if the input is exponentially distributed, bucket boundaries placed at quantiles of the exponential distribution restore uniform expected load. This requires distribution knowledge but recovers the O(n) expected bound.

8.2 Postman’s Sort

A folkloric variant where the input keys are strings or composite identifiers (postal codes, phone numbers) and the bucketing happens character-by-character, similar to Radix Sort’s most-significant-digit variant. Each bucket is recursively bucket-sorted on the next character. The structure is essentially MSD radix sort with bucket-sort framing.

8.3 Bucket Sort + External Memory

For very large datasets that do not fit in RAM, bucket sort generalizes nicely to external sorting: each bucket is written to a separate file on disk, the per-bucket sorts run independently (potentially in parallel on different machines), and the final concatenation is a sequential file merge. The bucketing-for-partitioning idea — distribute records into bins by a partitioner function, then sort each bin in isolation — is the structural template behind the shuffle phase of MapReduce-style distributed compute. It is important to be precise about what is reused, however: in Apache Spark’s modern sort-based shuffle, each ShuffleMapTask routes records into in-memory buckets via partitioner.partition(record.getKey()) — that is the bucket-sort-style partitioning step — but the actual sort within a partition is a general-purpose comparison sort (Spark’s AppendOnlyMap.destructiveSortedIterator() ultimately delegates to Java’s Array.sort(), which is TimSort) (SparkInternals shuffle-details; SPARK-7081). So bucket sort’s partitioning skeleton is what large-scale systems borrow; the in-partition sort is rarely bucket sort itself because partition data is usually neither uniformly distributed nor numerically bounded in the way bucket sort requires.

9. Pitfalls

Forgetting the idx == k clamp. When x == max_val, the formula floor(k · (x − min) / range) produces idx = k, which is out of bounds for a size-k bucket array. Crashes or silent overwrites result. Always clamp.
Assuming uniform distribution without verifying. The O(n) expected bound is tight to the uniform-distribution assumption. On Zipfian or clustered inputs, performance can degrade catastrophically to O(n²). Profile or sample the input before committing to bucket sort in production.
Picking k poorly. Too few buckets (k ≪ n) produces large buckets and per-bucket sort cost dominates. Too many buckets (k ≫ n) wastes memory and concatenation time. Standard choice is k ≈ n.
Sorting buckets with O(n log n) algorithms. Using Quicksort or Merge Sort for the per-bucket sort makes the total time O(n log(n / k)), which for k = n is O(n log 1) = O(n) only by coincidence (the log 1 = 0 argument). On average buckets of size > 1 the choice of insertion sort is genuinely better because of its lower constant factor on small inputs.
Non-numeric or non-orderable keys. Bucket sort fundamentally requires a numeric (or numerically-encodable) key with a known range. On keys without natural numeric encoding, fall back to a comparison sort or, for fixed-width strings, Radix Sort.
Floating-point precision around bucket boundaries. With high-precision floats and large k, the assignment floor(k · (x − min) / range) can produce boundary-misclassification due to rounding. Edge cases need careful handling, especially near the min and max extremes.

10. Diagram

flowchart TD
  Input["Input array<br/>n numeric values<br/>on range [min, max)"]
  Input --> Assign["Step 1: Assign to buckets<br/>idx = ⌊k·(x−min)/range⌋<br/>O(n)"]
  Assign --> B0["Bucket 0<br/>[min, min+range/k)"]
  Assign --> B1["Bucket 1<br/>[min+range/k, min+2·range/k)"]
  Assign --> Bdots["..."]
  Assign --> Bk["Bucket k−1<br/>[min+(k−1)·range/k, max]"]
  B0 --> S0["Insertion sort<br/>per-bucket"]
  B1 --> S1["Insertion sort<br/>per-bucket"]
  Bk --> Sk["Insertion sort<br/>per-bucket"]
  S0 --> Concat["Step 3: Concatenate<br/>buckets in order<br/>O(n + k)"]
  S1 --> Concat
  Sk --> Concat
  Concat --> Output["Sorted output<br/>O(n) expected total"]

What this diagram shows. The three-phase structure of bucket sort. Phase 1 (Assign): every input element is placed into one of k buckets via a numeric formula based on the element’s value relative to the range bounds. This phase is O(n) regardless of input distribution. Phase 2 (Per-Bucket Sort): each bucket is sorted independently with Insertion Sort (the expected per-bucket size of O(1) for uniform input keeps this phase O(n) total in expectation, but on skewed input one bucket can hold all n elements and degrade this phase to O(n²)). Phase 3 (Concatenate): the k buckets are walked in order and their contents stacked end-to-end into the output. The visual key insight is that bucket sort is embarrassingly parallel — Phase 2 can run on k different processors with no communication, and Phase 3 is a simple in-order concatenation. This parallelizability is a major reason bucket sort underlies the shuffle-and-sort phase of MapReduce-style distributed computation, even on non-uniform inputs where its sequential time bound degrades.

11. Common Interview Problems

Problem	Source	Why bucket sort applies
Sort an array of floats in `[0, 1)`	CLRS Ch. 8.4, classic interview	The canonical bucket-sort scenario
Maximum Gap	LeetCode 164	Bucket sort gives `O(n)` solution to find the max adjacent difference in a sorted version of the array; classic non-comparison-sort interview problem
Top K Frequent Elements	LeetCode 347	Bucket sort by frequency gives `O(n)` solution alternative to the heap-based `O(n log k)`
Sort Characters by Frequency	LeetCode 451	Same bucketing-by-frequency pattern
Approximate sorting in a streaming context	System design	Sketch-based bucketing supports approximate sort over data streams (related: Count-Min Sketch)

LeetCode 164 (Maximum Gap) is the most pointed application: the problem asks for the max difference between consecutive elements in a sorted version of the input, with the constraint that the algorithm run in O(n) time. Bucket sort is essentially the only non-comparison-based answer that achieves this — the trick is that you don’t even need to sort within each bucket, just track each bucket’s min and max, because adjacent elements in the sorted output cannot both be in the same bucket if buckets are sized appropriately.

12. Open Questions

What is the optimal k for non-uniform but known distributions? CLRS gives k = n for the uniform case; the analogous derivation for other distributions (Zipfian, exponential) is less standardized.
On modern hardware with deep cache hierarchies, does the bucket-distribution step’s random-write pattern (writing to k different bucket lists in arbitrary order) cause TLB misses that erode bucket sort’s theoretical advantage over cache-friendly comparison sorts like Quicksort?
How does bucket sort interact with sample-based partitioning techniques (as in parallel sort algorithms like Sample Sort)? The relationship between the two is structurally close but rarely treated as a continuum in textbooks.

13. Production Notes — Where Bucket Sort Actually Lives

Like its non-comparison cousins, bucket sort is not the general-purpose sort that any standard library exposes by default — C++ std::sort is introsort, Java Arrays.sort is Dual-Pivot Quicksort or TimSort, Python list.sort is TimSort, Go sort.Slice is pdqsort. These are all comparison sorts because they make no distributional assumption and accept any totally-ordered key. Bucket sort instead shows up wherever its assumptions do hold and the linear-time win is meaningful: floating-point pipelines that pre-normalize values into [0, 1) (graphics, scientific computing, hash-distribution analysis); the “find the maximum gap in O(n)” pattern (LeetCode 164 in interview prep, but also actual histogram-binning code in data-analysis libraries); and as the partitioning skeleton of distributed shuffle systems (Spark’s sort-based shuffle, MapReduce’s shuffle phase) where bucket sort hands records to partitions but a different sort runs inside each partition (Spark uses Array.sort → TimSort, per SparkInternals shuffle-details). Database systems use bucket-sort-like hash partitioning in parallel sort-merge joins for the same reason. The mental model worth carrying: bucket sort is rarely the whole sort algorithm in a production system, but its idea — distribute by a value-derived index, then sort each part — is one of the most-borrowed structures in systems engineering. Whenever you see “partition then sort”, that is bucket sort’s lineage even if the per-partition sort is something else.

14. See Also

Counting Sort — bucket sort’s discrete-integer cousin
Radix Sort — multi-pass bucketing on digit positions
Insertion Sort — the standard per-bucket sub-sort
Quicksort — the comparison-sort baseline that bucket sort tries to beat
Merge Sort — the worst-case-bounded comparison alternative
Tim Sort — adaptive comparison sort for general-purpose use
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Bucket Sort

Bucket Sort

1. Intuition — Sorting the Mail at the Post Office

2. Tiny Worked Example (n = 8 floats in `[0, 1)`)

Step 1 — Bucket assignment (`O(n)`)

Step 2 — Sort each bucket (`O(n)` expected)

Step 3 — Concatenate (`O(n + k)`)

Skewed Counter-Example

3. Pseudocode

4. Python Implementation

5. Complexity Analysis

5.1 Time

5.2 Space

5.3 Why the `O(n)` Bound Sidesteps the Comparison-Sort Lower Bound

6. Comparison with Counting Sort and Radix Sort

7. Stability and Adaptiveness

8. Variants

8.1 Generalized (Non-Uniform) Bucketing

8.2 Postman’s Sort

8.3 Bucket Sort + External Memory

9. Pitfalls

10. Diagram

11. Common Interview Problems

12. Open Questions

13. Production Notes — Where Bucket Sort Actually Lives

14. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Bucket Sort

Bucket Sort

1. Intuition — Sorting the Mail at the Post Office

2. Tiny Worked Example (n = 8 floats in [0, 1))

Step 1 — Bucket assignment (O(n))

Step 2 — Sort each bucket (O(n) expected)

Step 3 — Concatenate (O(n + k))

Skewed Counter-Example

3. Pseudocode

4. Python Implementation

5. Complexity Analysis

5.1 Time

5.2 Space

5.3 Why the O(n) Bound Sidesteps the Comparison-Sort Lower Bound

6. Comparison with Counting Sort and Radix Sort

7. Stability and Adaptiveness

8. Variants

8.1 Generalized (Non-Uniform) Bucketing

8.2 Postman’s Sort

8.3 Bucket Sort + External Memory

9. Pitfalls

10. Diagram

11. Common Interview Problems

12. Open Questions

13. Production Notes — Where Bucket Sort Actually Lives

14. See Also

Graph View

Table of Contents

Backlinks

2. Tiny Worked Example (n = 8 floats in `[0, 1)`)

Step 1 — Bucket assignment (`O(n)`)

Step 2 — Sort each bucket (`O(n)` expected)

Step 3 — Concatenate (`O(n + k)`)

5.3 Why the `O(n)` Bound Sidesteps the Comparison-Sort Lower Bound