Eleven Bits Per Pass

You need to sort n=105n = 10^5 records by a 32-bit unsigned key. LSD radix sort with a base of 2b2^b makes ⌈32/b⌉\lceil 32/b \rceil passes, and each pass costs about n+2bn + 2^b operations: nn to scatter the records and 2b2^b to clear and prefix-sum the count array. Total work is

W(b)=⌈32b⌉(n+2b)W(b) = \left\lceil \frac{32}{b} \right\rceil \left(n + 2^{b}\right)

Which of b=8b = 8, b=11b = 11, b=16b = 16, b=32b = 32 minimizes WW?

A

b=32b = 32, one pass and no repeated scatter work

B

b=11b = 11, about 3.1×1053.1 \times 10^5 operations

C

b=16b = 16, about 3.3×1053.3 \times 10^5 operations

D

b=8b = 8, about 4.0×1054.0 \times 10^5 operations