This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “MSD Radix Sort”.

1. Which of the following is not true about MSD radix sort?
A) its processing starts from the most significant digit
B) it is not a stable sort
C) it is an in place sorting algorithm
D) it is non comparison based sort

Explanation: For sorting the input data, MSD radix sort takes a non-constant amount of time. As a result, it’s not a sorting algorithm that works in real time.

2. MSD radix sort should be preferred over LSD radix sort when we have to maintain the original relative order.
A) True
B) False

Explanation: The MSD radix sort is not stable, while the LSD radix sort is. So, if we need to keep the original order, we can use LSD radix type.

3. What is the average time complexity of MSD radix sort (w= bits required to store each key)?
A) O(n + w)
B) O(n.w)
C) O(n2)
D) O(n log n)

Explanation: Radix sort has an O time complexity (n.w). When we have log n bits for each digit, it outperforms easy sort.

4. MSD radix sort is an in place sorting algorithm.
A) True
B) False

Explanation: For sorting the input data, MSD radix sort takes a non-constant amount of time. As a result, it’s not a sorting algorithm that works in real time.

5. Which of the following statement is not a stable sorting algorithm?
C) Counting sort
D) Pigeonhole sort

Explanation: The MSD radix type isn’t a long-term sort. It’s because the elements with similar values in the output array don’t appear in the same order as they did in the input array.

A) Radix sort performs better than quick sort when we have log n bits for every digit
B) Radix sort has better cache performance than quick sort
C) Radix sort has higher values of constant factor in asymptotic notation
D) Radix sort takes more space than quick sort

Explanation: Fast sort outperforms radix sort in terms of cache efficiency. Radix sort also takes up more room than fast sort.

A) radix sort performs better than quick sort when we have log n bits for every digit
B) radix sort has lesser space complexity
C) radix sort is not a comparison based sorting technique
D) radix sort has better cache performance than quick sort

Explanation: When we have log n bits for each digit, radix sort outperforms fast sort. Radix sort, on the other hand, takes up more room than easy sort.

8. What will be the order of elements of the array arr = {23, 67, 143, 654, 43} after first iteration of MSD sort is complete?
A) 23, 43, 67, 143, 654
B) 23, 67, 43, 143, 654
C) 23, 67, 143, 654, 43
D) 23, 143, 43, 654, 67

Explanation: The array is sorted in the first iteration by the most important digit, which is the hundreds place value. As a result, the elements will be in the following order: 23, 67, 43, 143, 654.

9. How many comparisons will be made to sort the array arr = {1, 5, 3, 8, 2} using MSD radix sort?
A) 5
B) 7
C) 9
D) 0

Explanation: Since MSD radix sort is a non-comparison sort, it can sort an array without performing any comparisons. As a result, the correct answer is 0.

10. What is the full form of MSD in MSD radix sort?
A) most significant digit
B) many significant digit
C) more significant digit
D) must significant digit

Explanation: The most significant digit is abbreviated as MSD. This algorithm is named after the fact that it starts processing with the most important digit.

11. Which of the following combines qualities of MSD radix sort and LSD radix sort?
C) 3 way radix quick sort

Explanation: The advantages of MSD and LSD radix sort are combined in forward radix sort. Separating the strings into classes is used to arrange them.

12. Which of the following is the most suitable definition of radix sort?
A) It is a non comparison based integer sort
B) It is a comparison based integer sort
C) It is a non comparison based non integer sort
D) It is a comparison based non integer sort

Explanation: Radix sort is an integer sort that isn’t dependent on contrast. It groups keys with the same significant position value to sort the given data.

13. Which of the following is an alternate name of MSD radix sort?