Question

LSD radix sort requires _____ passes to sort N elements.

(a) (w/logR)

(b) N(w/logR)

(c) (w/log(RN))

(d) (wN/log(N))

I have been asked this question by my college director while I was bunking the class.

My question comes from Sorting in portion Sorting of Data Structures & Algorithms II

Answer 1

Right option is (a) (w/logR)

The best I can explain: LSD radix sort sorts the N elements in  (w/logR) passes where w is the number of digits in largest number and R(radix) is extra space required for performing the sorting operation.