GATE CS 2007 Q14 — Searching, Sorting, Hashing

To find the sorting algorithm with the lowest worst-case time complexity, let us analyze the worst-case time complexity of each given option for an input of size $n$:

• Merge Sort: $\Theta(n \log n)$ in all cases (best, average, and worst) because it always divides the array into two halves and merges them.
• Bubble Sort: $\Theta(n^2)$ in the worst case (e.g., when the array is sorted in reverse order).
• Quick Sort: $\Theta(n^2)$ in the worst case (e.g., when the pivot consistently partitions the array into highly unbalanced subproblems of size $0$ and $n-1$).
• Selection Sort: $\Theta(n^2)$ in all cases because it always scans the remaining unsorted elements to find the minimum.

Comparing the worst-case complexities, we have:

Therefore, Merge Sort has the lowest worst-case complexity among the choices.