# Sort One Hundred Million Digits You must sort an unsorted collection of `100,000,000` integer digits, each in the range `0` through `9`. Describe an algorithm, its complexity, and a defensible order-of-magnitude runtime and memory estimate in a compiled language. Do not assume the digits were generated uniformly. ### Constraints & Assumptions - Every input value is an integer in `[0, 9]`. - The collection is already in memory; parsing text input is a separate cost. - Discuss both a packed one-byte representation and a typical wider integer representation. - A modern machine may have roughly `20-80 GB/s` sustainable memory bandwidth, but exact hardware is not fixed. ### Clarifying Questions to Ask - May the input buffer be overwritten, or is a separate output required? - What element width and container representation does the caller use? - Does the timing include allocation, parsing, validation, or only sorting resident values? - Is one CPU core required, and how warm are the caches and pages? - Is the output expected as individual elements or as ten `(digit, count)` pairs? ### What a Strong Answer Covers - Counting into ten buckets followed by deterministic output reconstruction. - `O(n + 10)` time and `O(10)` auxiliary state when overwriting the input. - Rough traffic and memory estimates based on element width and output policy. - Why comparison sorting is unnecessary and why input skew does not hurt counting sort. - The distinction between a bandwidth lower bound and a credible measured runtime. ### Follow-up Questions - How does the estimate change for `uint8` versus 64-bit integers? - Can multiple threads count without contending on the same ten counters? - When would returning counts be substantially cheaper than materializing sorted output? - Why might parsing decimal text dominate the sorting work?