Question

Which sorting algorithm has the same time complexity for all the cases-best, average, worst?

• A. Bubble Sort
• B. Quick Sort
• C. Radix Sort
• D. Merge Sort

Hint:

Merge Sort: \[ O(n\log n) \] for Best, Average and Worst cases.

Answer 1

The Correct Option is D

Concept: Sorting algorithms may exhibit different time complexities depending on input arrangement. We compare the complexities: \[ \text{Best Case} \] \[ \text{Average Case} \] \[ \text{Worst Case} \]

Step 1: Analyze Bubble Sort.
Bubble Sort may achieve \[ O(n) \] in the best case (optimized version) and \[ O(n^2) \] in the worst case. Hence not equal.

Step 2: Analyze Quick Sort.
Quick Sort: \[ O(n\log n) \] average case, \[ O(n^2) \] worst case. Hence not equal.

Step 3: Analyze Merge Sort.
Merge Sort recursively divides the array and merges. Its complexity remains \[ O(n\log n) \] for: \[ \text{Best Case} \] \[ \text{Average Case} \] \[ \text{Worst Case} \]

Step 4: Write the answer.
Therefore, \[ \boxed{\text{Merge Sort}} \] has identical asymptotic complexity in all cases. Hence option (D) is correct.