Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 47s17 days 22 hours 18 minutes 47 seconds.

Advanced - Arrays, Sorting and Searching · 4:01

Counting Sort and Radix Sort

Integers can be sorted without comparisons: counting sort counts each key, turns the counts into start positions and places items stably in O(n + K). LSD radix sort repeats a stable counting pass per digit, least significant first, which is why stability is the whole trick. We sort eight numbers in base 10, switch to bytes and signed keys, and measure radix against std::sort.

You will learn

Implement counting sort with counts, prefix-sum start positions and a stable placement in O(n + K)
Run LSD radix sort by hand and explain why every pass must be stable
Choose a digit size for 32-bit keys (bytes: 4 passes of 256 buckets) and handle signed keys by flipping the sign bit
Know when radix beats std::sort and why a larger digit is not automatically faster

Chapters

PreviousCoordinate Compression and MEX NextTernary Search and Golden-Section Search