Assuming the standard implementation of each algorithm (Bubble Sort and…
2024
Assuming the standard implementation of each algorithm (Bubble Sort and Insertion Sort with their usual best-case optimisation, e.g. an early-exit check), which of the following sorting algorithms has the same time complexity in the best, average, and worst cases?
- A.
Merge Sort
- B.
Quick Sort
- C.
Bubble Sort
- D.
Insertion Sort
- E.
None of the above
Attempted by 24 students.
Show answer & explanation
Correct answer: A
Correct answer: Merge Sort.
The question asks which sorting algorithm has the same time complexity in the best, average, and worst cases, assuming the standard implementation of each (with Bubble Sort and Insertion Sort using their usual best-case early-exit optimisation).
Merge Sort uses a divide-and-conquer strategy: it always splits the array into two halves (log n levels of division) and merges them in linear time at every level. This work is independent of how the input is arranged, so its running time is O(n log n) in the best, average, and worst case alike — the same complexity in all three cases.
Comparing the given options:
- Merge Sort: O(n log n) best = average = worst (uniform).
- Quick Sort: O(n log n) best and average, but O(n^2) in the worst case (e.g. an already-sorted array with a poor pivot).
- Bubble Sort (with early-exit): O(n) best (already sorted), but O(n^2) average and worst.
- Insertion Sort: O(n) best (already sorted), but O(n^2) average and worst.
Only Merge Sort keeps the same O(n log n) bound across all three cases, so it is the correct choice.