Worked examples — Bucket sort — uniform distributions

This page drills the parent topic through every case class bucket sort can throw at you. We start by mapping the whole terrain, then walk one fully-worked example per cell.

---

The scenario matrix

Bucket sort has a small number of "shapes" the input can take. Every shape stresses a different part of the algorithm. Here is the full list — every later example is tagged with the cell it covers.

#	Cell class	What it stresses	Example
A	Typical uniform input in $[0,1)$	the normal happy path, $O(n)$	Ex 1
B	Boundary value $x=1.0$ or $x=hi$	the out-of-range index bug	Ex 2
C	Zero / empty buckets	reading empty slots, degenerate	Ex 3
D	Clumped / skewed input (worst case)	all-in-one-bucket, $O(n^2)$	Ex 4
E	Rescaled range $[lo,hi)$	the normalize-first step	Ex 5
F	Cost accounting via $E[n_i^2]$	the probability analysis, numbers	Ex 6
G	Negative + fractional real-world values	mapping messy units to $[0,1)$	Ex 7
H	Exam twist — duplicates & stability	ties inside one bucket	Ex 8
I	Limiting behaviour — $n=1$ and huge $n$	degenerate small case + trend	Ex 9

Nine cells, nine examples. Let's cover them all.

---

Ex 1 — Cell A: the typical uniform run

Steps.

1. Compute each index $\lfloor 8x\rfloor$. Why this step? The index formula turns a value into an address — the whole reason bucket sort skips comparisons.

   • $0.42\to \lfloor 3.36\rfloor =3$; $0.88\to \lfloor 7.04\rfloor =7$; $0.05\to 0$; $0.55\to \lfloor 4.4\rfloor =4$
   • $0.61\to \lfloor 4.88\rfloor =4$; $0.13\to 1$; $0.90\to \lfloor 7.2\rfloor =7$; $0.34\to \lfloor 2.72\rfloor =2$

2. Drop into buckets. Why this step? This is the "Scatter" S — grouping without ordering. $b_0=[0.05],b_1=[0.13],b_2=[0.34],b_3=[0.42],b_4=[0.55,0.61],b_5=[],b_6=[],b_7=[0.88,0.90]$

3. Sort each non-empty bucket (only $b_4,b_7$ have $\ge 2$ items; both already ascending). Why this step? Buckets are tiny, so insertion sort is essentially free.

4. Concatenate left to right, skipping empties: $0.05,0.13,0.34,0.42,0.55,0.61,0.88,0.90$

Verify: $0.55$ landed in bucket 4 (forecast). Buckets 5 and 6 are empty — 2 empty buckets. Output is strictly increasing and is a permutation of the input. ✅

---

Ex 2 — Cell B: the boundary value $x=1.0$

Steps.

1. Compute naive indices. $\lfloor 3\cdot 0.5\rfloor =1$, $\lfloor 3\cdot 0.2\rfloor =0$, $\lfloor 3\cdot 1.0\rfloor =3$. Why this step? To expose the failure at the closed endpoint.

2. Notice the crash. Valid indices are $0,1,2$. Index $3$ is out of range — buckets[3] throws. Why this step? This is exactly the third [!mistake] in the parent note, made concrete.

3. Apply the clamp fix: idx = min(int(n*x), n-1). Why this step? It folds the single boundary point $x=1.0$ back into the top bucket without disturbing any interior value. Now $1.0\to \min (3,2)=2$.

4. Re-bucket & concatenate: $b_0=[0.2],b_1=[0.5],b_2=[1.0]\Rightarrow 0.2,0.5,1.0$.

Verify: Naive index for $1.0$ is 3, which is invalid ($\ge n$). Clamped index is 2. Sorted output [0.2, 0.5, 1.0] is correct. ✅

---

Ex 3 — Cell C: mostly-empty (degenerate sparse) input

Steps.

1. Indices: $\lfloor 6\cdot 0.11\rfloor =0$, $\lfloor 6\cdot 0.19\rfloor =1$. Why this step? Small inputs cluster into low buckets, leaving many empty — the sparse degenerate shape.

2. Buckets: $b_0=[0.11],b_1=[0.19],b_2=b_3=b_4=b_5=[]$. Why this step? Shows the concatenation loop must gracefully skip 4 empty lists.

3. Concatenate: $0.11,0.19$. The empties contribute nothing.

Verify: 2 non-empty buckets ($b_0,b_1$), 4 empty. Output [0.11, 0.19] sorted. ✅

---

Ex 4 — Cell D: the worst case (everything clumps)

Steps.

1. Indices: $\lfloor 5\cdot 0.90\rfloor =4$, $\lfloor 5\cdot 0.95\rfloor =4$, $\lfloor 5\cdot 0.91\rfloor =4$, $\lfloor 5\cdot 0.99\rfloor =4$, $\lfloor 5\cdot 0.93\rfloor =4$. Why this step? All values live in $[0.8,1.0)$, which is the single range mapping to bucket 4.

2. All five land in $b_4$: $b_4=[0.90,0.95,0.91,0.99,0.93]$, every other bucket empty. Why this step? This is the definition of the worst case — one bucket holds all $n$ items.

3. Cost of sorting $b_4$: insertion sort on $m=5$ items costs $\propto m^2=25$ comparisons in the worst case. With bucket size $=n$, this is $O(n^2)$. Why this step? It shows the average-case $O(n)$ proof collapses when the uniform assumption is violated.

4. Concatenate (only $b_4$ contributes): $0.90,0.91,0.93,0.95,0.99$.

Verify: All 5 values in bucket 4; worst-case comparisons $\le \left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ (insertion sort), so $\Theta (m^2)$ growth. Output [0.90, 0.91, 0.93, 0.95, 0.99] correct. ✅

---

Ex 5 — Cell E: rescaled range $[lo,hi)$

Steps.

1. Normalize with $\text{index}=\lfloor n\cdot \frac{x-lo}{hi-lo}\rfloor$, here $lo=10,hi=50$, width $=40$. Why this step? Bucketing only knows $[0,1)$; we must squeeze the original units into it first, keeping slots equal-width in the real units (each bucket spans $40/4=10$ units).

2. Compute:

   • $30:\lfloor 4\cdot \frac{20}{40}\rfloor =\lfloor 2.0\rfloor =2$
   • $12:\lfloor 4\cdot \frac{2}{40}\rfloor =\lfloor 0.2\rfloor =0$
   • $47:\lfloor 4\cdot \frac{37}{40}\rfloor =\lfloor 3.7\rfloor =3$
   • $25:\lfloor 4\cdot \frac{15}{40}\rfloor =\lfloor 1.5\rfloor =1$

3. Buckets: $b_0=[12],b_1=[25],b_2=[30],b_3=[47]$ — one each.

4. Concatenate: $12,25,30,47$.

Verify: $30\to$ bucket 2. Sorted output [12, 25, 30, 47]. Bucket spans are 10 units each. ✅

---

Ex 6 — Cell F: the cost analysis in numbers

Steps.

1. Model. Each element lands in bucket $i$ with $p=1/n=1/100$, independently, so $n_i\sim \text{Binomial}(100,0.01)$. See Binomial distribution. Why this step? Uniform input ⇒ equal per-bucket chance ⇒ this exact distribution.

2. Mean: $E[n_i]=np=100\cdot 0.01=1$. Why this step? Confirms the design goal: one item per bucket on average.

3. Variance: $\mathrm{Var}(n_i)=np(1-p)=100\cdot 0.01\cdot 0.99=0.99$. Why this step? The spread measures "clumping" — how far bucket loads wander from 1.

4. Second moment via $E[X^2]=\mathrm{Var}+(E[X]{)}^2$: $E[n_i^2]=0.99+1^2=1.99=2-\frac{1}{100}.$ Why this step? This matches the parent's $2-\frac{1}{n}$ — the constant that makes the algorithm linear.

5. Total quadratic work: ${\sum }_{i=0}^{99}E[n_i^2]=100\cdot 1.99=199\approx 2n$. Why this step? Total insertion-sort cost $\propto 2n$ = linear, the punchline.

Verify: $E[n_i]=1$, $\mathrm{Var}=0.99$, $E[n_i^2]=1.99$, and $\sum =199$. ✅

---

Ex 7 — Cell G: real-world word problem (negative + fractional)

Steps.

1. Set range: $lo=-10,hi=20$, width $=30$, so each bucket spans $30/5=6$ °C. Why this step? Negative values are no obstacle — normalization handles the shift automatically.

2. Normalize & floor with $\lfloor n\frac{x-lo}{hi-lo}\rfloor$:

   • $-3.5:\lfloor 5\cdot \frac{6.5}{30}\rfloor =\lfloor 1.083\rfloor =1$
   • $12.0:\lfloor 5\cdot \frac{22}{30}\rfloor =\lfloor 3.667\rfloor =3$
   • $-8.0:\lfloor 5\cdot \frac{2}{30}\rfloor =\lfloor 0.333\rfloor =0$
   • $4.5:\lfloor 5\cdot \frac{14.5}{30}\rfloor =\lfloor 2.417\rfloor =2$
   • $19.5:\lfloor 5\cdot \frac{29.5}{30}\rfloor =\lfloor 4.917\rfloor =4$

3. Buckets: $b_0=[-8.0],b_1=[-3.5],b_2=[4.5],b_3=[12.0],b_4=[19.5]$.

4. Concatenate: $-8.0,-3.5,4.5,12.0,19.5$ (°C).

Verify: $-3.5\to$ bucket 1. Sorted [-8.0, -3.5, 4.5, 12.0, 19.5] °C. ✅

---

Ex 8 — Cell H: exam twist — duplicates & stability

Steps.

1. Indices on the key: $\lfloor 4\cdot 0.3\rfloor =1$ (three times), $\lfloor 4\cdot 0.1\rfloor =0$. Why this step? Equal keys ⇒ equal indices ⇒ same bucket. Ties are inevitable here.

2. Bucket $b_1$ receives, in scatter order, $(0.3{,}^{\prime }{a}^{\prime }),(0.3{,}^{\prime }{b}^{\prime }),(0.3{,}^{\prime }{d}^{\prime })$. Why this step? The scatter loop appends in input order, preserving original sequence.

3. Sort $b_1$ stably. A stable sort on equal keys keeps the existing order: ${}^{\prime }{a}^{\prime }{,}^{\prime }{b}^{\prime }{,}^{\prime }{d}^{\prime }$. Why this step? Stability of the whole algorithm hinges on the per-bucket sort being stable.

4. Concatenate: $(0.1{,}^{\prime }{c}^{\prime }),(0.3{,}^{\prime }{a}^{\prime }),(0.3{,}^{\prime }{b}^{\prime }),(0.3{,}^{\prime }{d}^{\prime })$.

Recall When is bucket sort stable?

Only if each bucket's internal sort is stable and elements are appended in input order. Which per-bucket sort keeps ties in order? ::: A stable one (e.g. insertion sort or a stable merge).

Verify: All three $0.3$ records in bucket 1; tie order a,b,d preserved. Output tags in order: c,a,b,d. ✅

---

Ex 9 — Cell I: limiting behaviour ($n=1$ and $n\to \infty$)

Steps.

1. (a) Degenerate $n=1$. Index $=\lfloor 1\cdot 0.7\rfloor =0$. The lone bucket $b_0=[0.7]$. Why this step? The smallest legal input must still behave — one bucket, one item, zero swaps.

2. Sort & concatenate: a 1-element list is already sorted → output [0.7]. Why this step? Confirms the algorithm is a no-op on trivial input (no crash, no infinite loop).

3. (b) Limit of $E[n_i^2]=2-\frac{1}{n}$: as $n\to \infty$, $\frac{1}{n}\to 0$, so $E[n_i^2]\to 2$. Why this step? Shows the per-bucket quadratic work is bounded above by 2 forever — it never grows with $n$, which is why the total stays $O(n)$.

4. Bound sanity: for every $n\ge 1$, $1\le 2-\frac{1}{n}<2$. Even the smallest $n=1$ gives $2-1=1$. Why this step? Every case, from $n=1$ to $n\to \infty$, lives in $[1,2)$ — no scenario escapes linearity.

Verify: (a) index $=0$, output [0.7]. (b) ${\lim }_{n\to \infty }(2-\frac{1}{n})=2$; at $n=1$ the value is $1$; bound $1\le 2-\frac{1}{n}<2$ holds. ✅

---

---

Connections

• Bucket sort — uniform distributions — the parent this page drills.
• Binomial distribution — powers Ex 6's $E[n_i^2]$.
• Insertion sort — the per-bucket sort in Ex 1, 4, 8.
• Counting sort — the "one bucket per key" limit relevant to Ex 8's duplicates.
• Radix sort — repeated normalized bucketing generalizing Ex 5, 7.
• Comparison sort lower bound — why the address trick (Ex 1) beats $n\log n$.
• Hashing — same value-as-address idea seen in every scatter step.