GATE CS 1992 Q02 — Searching, Sorting, Hashing

To sort $n$ integers in the range $[1 \dots n^3]$ in $O(n)$ time, we analyze the given sorting algorithms:

1. Comparison-based Sorting Algorithms (Heap Sort, Quick Sort, Merge Sort):

   Any comparison-based sorting algorithm has a lower bound of $\Omega(n \log n)$ in the worst case. Therefore, Heap sort, Quick sort, and Merge sort cannot achieve $O(n)$ time complexity.

2. Radix Sort:

   Radix sort is a non-comparison-based sorting algorithm. It sorts $n$ keys of $d$ digits where each digit can take up to $b$ different values (base $b$) in $O(d(n + b))$ time using Counting Sort as a stable sorting subroutine.

   For numbers in the range $[1 \dots n^3]$, we can represent them in base $b = n$. In base $n$, the maximum number of digits $d$ required to represent any number up to $n^3$ is:

   $$d = \log_n(n^3) = 3$$

   Substituting $b = n$ and $d = 3$ into the Radix sort time complexity formula:

   $$T(n) = O(3 \cdot (n + n)) = O(n)$$

Thus, Radix sort can be used to sort the given numbers in $O(n)$ time.