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

@Kimo123 

The modification you are suggesting is making Bubble sort more efficient than others and it's not the worst case of bubble sorting, we need to compare every algorithm worst case times. Bubble's sort is O(n square).

---

Ans: Option A (Merge Sort)

Extra points regarding Best and Worst Case:

1. Merge sort and heap sort  ⇒ lowest worst-case complexity (𝜃(nlogn))

2. Insertion sort ⇒ lowest best case complexity (O(n))

3. Selection sort ⇒ Min number of swaps in worst case

---

Algorithm	Worst-Case Time Complexity
Merge Sort	O(nlog⁡n)
Bubble Sort	O(n^2)
Quick Sort	O(n^2) (bad pivot case)
Selection Sort	O(n^2)

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)