Which of the following algorithms sort 𝑛 integers, having the range \(0\) to…
2015
Which of the following algorithms sort 𝑛 integers, having the range \(0\) to \((𝑛^2−1)\), in ascending order in \(𝑂(𝑛)\) time?
- A.
Selection sort
- B.
Bubble sort
- C.
Radix sort
- D.
Insertion sort
Attempted by 170 students.
Show answer & explanation
Correct answer: C
Key idea: use radix sort with base equal to n so each number has at most two digits.
Choose base b = n. Every integer in the range 0 to n^2 − 1 can be written with at most 2 digits in base n (a low digit and a high digit).
Use a stable counting sort to sort the numbers by the least significant digit. Counting sort on one digit takes O(n + b) time; here b = n, so this pass is O(n).
Use a stable counting sort to sort the result by the most significant digit. This second pass is also O(n). Because the sorts are stable, the two passes produce a correctly ordered list.
Total time: two passes × O(n) = O(n).
Why other given algorithms do not achieve O(n):
Selection sort, bubble sort, and insertion sort are comparison-based procedures with Θ(n^2) worst-case time; they cannot guarantee linear time in this setting.
Counting sort alone would be O(n + k) where k is the range size (k = n^2), giving O(n^2) overall. Using counting sort as the stable subroutine inside radix sort with base n avoids that large k.
Conclusion: Radix sort (with base n and two stable counting-sort passes) sorts the given integers in O(n) time.