GATE CSE 2007 | Question: 14

Question

Which of the following sorting algorithms has the lowest worse-case complexity?

• A. Merge sort

• B. Bubble sort

• C. Quick sort

• D. Selection sort

Comments

i think Bubble sort could be the answer , because if we use modification : Early termination, i.e No swapping in the inner loop then it will be O(n)

---

if we do not go with bubble sort early termination modification then ---merge sort if right answer, heap sort also having lowest worst case time complexity O(nlogn) as like merge sort.

Answer 1

Correct Option: A

Irrespective of the input, merge sort always have a time complexity of  $\Theta(n \log n)$.

Answer 2

Merge sort has lowest worst case time complexity i.e O(nlogn)

Answer 3

MERGE SORT all others have the worst case complexity O(n^2)

Answer 4

Irrespective of everything worst case for quick sort,bubble srt and selections sort  is  O(n^2)

 

Whereas for merge sort it is O(nlog n)