Sort One Hundred Million Digits

Sort One Hundred Million Digits

You are given an array of 100,000,000 (10^8) integers, where each value is an integer digit between 0 and 9 inclusive.

Implement an in-place sorting algorithm that runs in O(N) time using minimal auxiliary space. Rather than using a general-purpose comparison sort (which requires O(N log N) time), utilize counting sort with a fixed array of 10 frequency counters.

After specifying the algorithm, be prepared to discuss memory representation choices (e.g., 64-bit integers vs. packed bytes), cache/memory bandwidth bottlenecks, and a realistic runtime estimate on modern hardware.

Function Signature

def sort_digits(digits: bytearray) -> None:
    """
    Sorts the bytearray of digits (0-9) in-place.
    """
    pass

Input and Output Format

• Input: A bytearray digits containing 10^8 elements, where each element is an integer in the range [0, 9].
• Output: None. The input digits must be modified in-place to be sorted in non-decreasing order.

Constraints

• len(digits) == 100_000_000 (for testing, functions should handle arbitrary lengths 0 <= N <= 10^9).
• 0 <= digits[i] <= 9 for all i.
• Auxiliary space complexity: O(1) (at most 10 integer counters).

Examples

Example 1 (Miniature)

input_data = bytearray([4, 2, 0, 9, 2, 4, 1])
sort_digits(input_data)
print(list(input_data))
# Output: [0, 1, 2, 2, 4, 4, 9]

Explanation: Counts are 0:1, 1:1, 2:2, 4:2, 9:1. The original array is overwritten with digits in sorted order.

Edge Cases

• Highly skewed distributions (e.g., all 10^8 digits are 0, or missing digits).
• Empty or single-element inputs (len(digits) <= 1).