Radix and Counting Sort feel simple until a question asks for the list after one digit pass or hides the running time inside n, d and k. Marks leak there. Attempt each question before reading its explanation, and use the exam-and-year labels to prioritise previous-year practice. Rebuild the comparison versus non-comparison split with Sorting Algorithms: Complexity and Comparison if needed.
Comparison-based or not? Start here
Radix, Counting and Bucket sort do not compare pairs of keys. They place keys by digit, count or range. Quick Sort, Merge Sort and Heap Sort instead decide order through comparisons.
Q1. IBPS 2025
Which of the following sorting algorithms does not use comparison operations?
(a) Quick Sort
(b) Merge Sort
(c) Radix Sort
(d) Heap Sort
(e) Insertion Sort
Correct option: (c). Radix Sort orders keys by processing digits with a stable counting step, not by comparing two keys directly. The other four determine order through pairwise comparisons. See the solved page.
Q2. Concept check
Which of the following is a comparison-based sorting algorithm?
(a) Counting Sort
(b) Radix Sort
(c) Bucket Sort
(d) Quick Sort
Correct option: (d). Quick Sort compares elements with a pivot during partitioning. Counting, Radix and Bucket sort derive their main ordering from counts, digits and range placement. That distinction lets them avoid the comparison-sorting lower bound when their key-range assumptions hold.
Q3. LTI Mindtree 2024
Which of the following statements is not true about comparison-based sorting algorithms?
(a) The minimum possible time complexity of a comparison-based sorting algorithm is O(n*Logn) for a random input array.
(b) Any comparison-based sorting algorithm can be made stable by using position as a parameter when two elements are compared.
(c) The Counting sort is not a sorting algorithm based on comparison.
(d) Heap Sort is not a comparison-based sorting algorithm.
Correct option: (d). The question asks for the false statement. Heap Sort compares keys while restoring the heap, so calling it non-comparison-based is wrong; statements (a), (b) and (c) are true. See the solved page.
Radix sort by hand, with counting sort as the engine
LSD Radix Sort makes one pass per digit, moving from the least significant digit to the most significant. Every pass must be stable so that the order created by earlier digit passes survives. Counting Sort supplies that stable pass: count each digit value, convert counts into running positions, then place keys in their slots.
For a small example, sort A = [1, 4, 1, 2, 7, 5, 2], where values range from 0 to 7. The counts for values 0 through 7 are [0, 2, 2, 0, 1, 1, 0, 1]. Their prefix totals are [0, 2, 4, 4, 5, 6, 6, 7], and stable placement gives [1, 1, 2, 2, 4, 5, 7]. Count-array work costs O(k), while counting and stable placement cost O(n), so the total is O(n + k).
Q4. BEL 2023, Computer Science, Probationary Engineer
Sort the following list using radix sort: 429, 557, 757, 939, 536, 820, 455. What is the output of the algorithm after the first pass?
(a) 820, 455, 536, 557, 757, 429, 939
(b) 429, 455, 557, 536, 757, 820, 939
(c) 820, 429, 536, 939, 455, 557, 757
(d) 939, 820, 757, 557, 536, 455, 429
Correct option: (a). The units digits are 9, 7, 7, 9, 6, 0, 5. Stable buckets give 0: 820; 5: 455; 6: 536; 7: 557, 757; 9: 429, 939, so the output is 820, 455, 536, 557, 757, 429, 939. Ties keep their input order. See the solved page.
Q5. DSSSB 2021, Computer Science, TGT
Sort the following list using Radix sort algorithm. 329, 457, 839, 436, 720, 355, 657. What is the output of the algorithm after 2nd pass?
(a) 720, 355, 436, 457, 657, 329, 839
(b) 720, 329, 436, 839, 355, 457, 657
(c) 329, 355, 436, 457, 657, 720, 839
(d) 355, 329, 457, 436, 720, 657, 839
Correct option: (b). Pass 1 on units digits 9, 7, 9, 6, 0, 5, 7 gives 720, 355, 436, 457, 657, 329, 839, which is distractor (a). Its tens digits are 2, 5, 3, 5, 5, 2, 3, so stable groups 2, 3, 5 give 720, 329, 436, 839, 355, 457, 657. Option (c) is the result after all three passes. See the solved page.
The time complexity identities
Q6. UGC NET 2016, Computer Science, Paper 2
If there are n integers to sort, each integer has d digits, and each digit is in the set {1, 2, …, k}, radix sort can sort the numbers in :
(a) O(k(n+d))
(b) O(d(n+k))
(c) O((n+k) lg d)
(d) O((n+d) lg k)
Correct option: (b). There are d passes. A Counting Sort pass across n keys and k digit values costs O(n + k), giving O(d(n + k)); when k = O(n), this becomes O(dn). See the solved page.
Q7. GATE 2008, Computer Science, Information Technology paper
If we use Radix Sort to sort n integers in the range (n^(k/2), n^k], for some k>0 which is independent of n, the time taken would be?
(a) Theta(n)
(b) Theta(kn)
(c) Theta(n logn)
(d) Theta(n^2)
Correct option: (b). A key no larger than n^k needs at most k + 1 base-n digits, which is Theta(k). With radix n, each pass costs Theta(n + n) = Theta(n), so all passes cost Theta(kn). Since k is independent of n, this is also linear in n, but the keyed option keeps k explicit. See the solved page.
Operation-count numericals
These questions use n times digits times base as their counting model. Here, “comparisons” means per-digit placement work, not literal comparisons between keys.
Q8. ISRO 2023, Computer Science
What is the maximum number of comparisons needed to sort 6 items using radix sort, if each number is a 3-digit decimal number?
(a) 120
(b) 180
(c) 210
(d) 360
Correct option: (b). Here n = 6, d = 3 and decimal base k = 10. The question's model gives 6 times 3 times 10 = 180. See the solved page.
Q9. UGC NET 2018, Computer Science, Paper 2
The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number) :
(a) 45
(b) 72
(c) 360
(d) 450
Correct option: (c). Octal uses base 8. Each pass accounts for 9 times 8 = 72 units of work, and five passes give 72 times 5 = 360. See the solved page.
Sorting integers in a bounded range
For keys from 0 to n^2 minus 1, base n representation uses at most two digits. Two stable Counting Sort passes can therefore finish in linear time.
Q10. UGC NET 2019, Computer Science, Paper 2
Which of the following is best running time to sort n integers in the range 0 to n^2-1 ?
(a) O(log n)
(b) O(n)
(c) O(n log n)
(d) O(n^2)
Correct option: (b). Every key has at most two base-n digits. Each Counting Sort pass costs O(n + n) = O(n), so two passes still cost O(n). See the solved page.
Q11. UGC NET 2015, Computer Science, Paper 2
Which of the following algorithms sort n integers, having the range 0 to (n^2-1), in ascending order in O(n) time?
(a) Selection sort
(b) Bubble sort
(c) Radix sort
(d) Insertion sort
Correct option: (c). Radix Sort uses two base-n digit passes and reaches O(n). Selection, Bubble and Insertion Sort take Omega(n^2) time in the worst case. See the solved page.
Q12. Concept check, Bucket Sort
What is the time complexity of a bucket sort algorithm?
(a) O(n^2)
(b) O(n log n)
(c) O(n + k)
(d) O(n)
Correct option: (c). With n elements spread across k buckets and a roughly uniform distribution, Bucket Sort takes expected O(n + k), including distribution and bucket traversal. If every element lands in one bucket and that bucket is sorted quadratically, the worst case is O(n^2). Counting Sort shares the O(n + k) count-and-place shape.
How these are examined, and the short version
The recurring patterns are the comparison versus non-comparison split, the LSD hand trace where a pass-1 result becomes a distractor, and the O(d(n + k)) identity. That identity becomes linear when the digit count is constant and the range is polynomial in n. If a question exposed a gap, revisit stability or the base-n digit step before solving more questions.
Rebuild the mechanism through GATE CS Exam preparation, then attempt full previous-year sets in GATE Guidance by Sanchit Sir. Placement and semester learners can use CS Fundamentals for Placements by Sanchit Sir. Continue with Data Structures MCQs for a broader mixed set.
Solve first, review every miss, then return to this set one week later. The second attempt at the trace questions is where stable digit passes become automatic.
