Sorting algorithms · 7/7
Distributes by range, sorts locally and concatenates.
Each bucket covers an ordered interval. Sort inside each bucket and concatenate left to right.
The cumulative distribution function (CDF) of a random variable X gives the probability that X does not exceed a threshold x. It is nondecreasing, lies between 0 and 1, and approaches 0 or 1 at the ends of the number line.
If F is continuous and known, F(X) is uniform between 0 and 1. For k buckets numbered 0 to k−1, use b(x) = min(k−1, ⌊k F(x)⌋). Bucket boundaries are the quantiles F⁻¹(i/k): each interval has model probability 1/k. The minimum handles F(x)=1.
For a continuous variable with density f, integrate: F(x) = ∫₋∞ˣ f(t) dt. If X is uniform from a to b, within that interval F(x) = (x−a)/(b−a). Outside [a,b] it is 0 to the left and 1 to the right. For example, on [0, 100], F(35)=0.35: with 10 buckets, 35 goes to bucket 3.
Sum the probabilities of values no greater than x: F(x) is the sum of P(X=v) over all v≤x. If P(X=1)=0.2, P(X=2)=0.5 and P(X=3)=0.3, then F(2)=0.7. The CDF has jumps: applying F(X) directly does not balance buckets when many values are equal.
From a sample of m observations, F̂ₘ(x) = #{values ≤ x}/m. For 1, 2, 2, 5, 8 we get F̂₅(2)=3/5. A representative sample can suggest quantiles, but estimation has a cost and errors can leave buckets unbalanced.
Following the example in Algoritmi.pdf, consider points uniformly distributed over the area of a disk of radius R. If the key is angle θ, sectors have width 2π/k and FΘ(θ)=θ/(2π). If the key is distance r from the centre, equal width rings are not balanced: area grows with r². Use equal area rings instead.
0 ≤ θ < 2π · FΘ(θ) = θ/(2π) · b(θ) = ⌊kθ/(2π)⌋
With k=8, a point at θ=π/2 goes to bucket 2.
0 ≤ r ≤ R · Fᵣ(r) = πr²/(πR²) = (r/R)² · rᵢ = R√(i/k)
With R=10 and k=4, the first ring ends at r₁=5; each ring covers 25% of the area.
Select a point in the disk, or advance with the controls.
Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.
Use 2 to 16 values. This visualizer accepts values from 0 to 999.
create k empty bucketsfor value in A index ← bucketFor(value) append value to bucket[index]for each bucket sort bucketconcatenate all buckets into AThe highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.
Well-balanced buckets make distribution and collection Θ(n+k).
Under a uniform model with k=Θ(n), expected bucket size is constant: Θ(n+k).
If every value lands in one insertion-sorted bucket, time is Θ(n²).
The k buckets hold n total items: Θ(n+k). Stability depends on the local sort.
Stability concerns the relative order of elements with equal keys.
This classification refers to the version shown on this page.
Effective when a roughly uniform distribution is known.
Bucket boundaries are part of the algorithm; poor boundaries cause imbalance.