Before trusting bucket sort on a billion GPS longitudes claimed uniform, what do you verify?

### Treat "uniform" as a hypothesis Someone proposes bucket sort for a billion longitude values on the grounds that longitudes are uniform over their range. The engineering answer is not yes or no; it is "show me the histogram". Bucket sort is the one sort in the family whose bound is a claim about the *data* rather than the *key format*, so the data is what has to be inspected. In this specific case the claim is almost certainly false. Positions come from where people and devices are, so they pile up over inhabited land and thin out over oceans and empty terrain. A uniform-looking *range* is not a uniform *distribution*, and the two get conflated constantly. ### How to actually check **Sample and bin at the real resolution.** Draw a large random sample and histogram it into exactly the `k` buckets you intend to use. Binning at a coarser resolution hides the clumping you care about — a distribution can look reasonable at 100 bins and be catastrophic at 100,000. **Read the maximum, not the mean.** Average occupancy is `n/k` for every possible distribution; it carries no information. What determines your cost is the largest bucket and the tail of the occupancy distribution. Useful summary numbers: max occupancy divided by expected occupancy, the 99.9th percentile of occupancy, and the fraction of keys living in the top few buckets. A ratio near one means the scatter is doing its job; a ratio in the hundreds means you are about to run the inner sort on a large fraction of the data. **Check for exact duplicates.** Rounded or snapped coordinates produce enormous runs of identical values. Identical keys never separate no matter how the range is partitioned, and no amount of recursion or extra buckets helps. If duplicates are heavy, either handle them explicitly with a distinct-value tally or drop the distribution sort. **Ask who controls the keys.** An expectation over a distribution promises nothing against a party that chooses the input. If the values arrive from external callers, someone can send a billion keys that all land in one bucket, and you have handed them a way to convert a linear job into a quadratic one. Data you generate yourself is a different risk profile from data you are handed. **Ask whether the shape is stable.** A histogram is a snapshot. Coverage expands into new regions, a new device fleet ships, a partner's feed changes its rounding. A bound justified by a measurement taken once is only as good as the re-measurement schedule, so if you rely on the shape, monitor it — recording max bucket occupancy per run is cheap and turns a silent regression into an alert. ### The parameters you must choose deliberately **Bucket count `k`.** This is a two-sided tradeoff, and at a billion keys both sides bite: - Too small: buckets are large and the inner sort dominates. The whole point of the scatter is to make phase two trivial. - Too large: the gather sweeps O(k) slots, most of them empty, and every bucket carries allocation and header overhead. The textbook `k = n` means a billion containers — the directory alone can outweigh the data, and it destroys locality. The sane target is an expected occupancy of a small constant, with `k` also chosen so that the bucket directory fits comfortably in memory and, ideally, so that work on one bucket stays cache-resident. **Memory.** Bucket sort is not in-place: O(n + k) auxiliary space, effectively a second copy of the data plus the directory. At a billion keys that may be the entire decision, independent of asymptotics — an in-place comparison sort that never allocates can beat a theoretically faster sort you cannot fit. **The fallback.** Cap the damage: if a bucket exceeds a threshold, sort it with an O(m log m) comparison sort instead of the quadratic inner sort. The worst case becomes O(n log n) rather than O(n²), which converts a stall into a slowdown. This is the same instinct behind hybrid comparison sorts that switch strategy when a recursion goes bad. ### The decision, honestly framed Even when the measurement comes back favourable, ask what you win. Bucket sort's payoff over a well-tuned comparison sort on real hardware is often a modest constant factor, and you are paying for it with extra memory, a distribution assumption, a fallback path, and a monitoring obligation that every future maintainer inherits. Take the trade when the sort is genuinely on the critical path, the data is yours and measured, and the win is demonstrated on production-shaped input — not on the strength of an asymptotic label. Independent buckets do parallelize beautifully, which is often a stronger practical argument in its favour than the asymptotics are.