Vidyalelo
Data Structure · Q38

Sorting Algorithms

Programming · Data Structure · question 38

Q38

Which sorting algorithm has a time complexity of O(n log n) in the worst case and is not stable?

A.
Counting Sort
B.
Heap Sort
Answer
C.
Merge Sort
D.
Quick Sort

Answer: Option B

Solution

Answer: Option B
Solution:
Heap Sort is a sorting algorithm with a worst-case time complexity of O(n log n). It is not stable because the relative order of equal elements may not be preserved during the sorting process.

Option A: Counting Sort is not correct because it has a time complexity of O(n + k), where k is the range of the input, and it is stable.

Option C: Merge Sort has a worst-case time complexity of O(n log n), but it is a stable sorting algorithm.

Option D: Quick Sort has an average-case time complexity of O(n log n), but its worst-case time complexity is O(n²). It is also not stable.

Therefore, the correct answer is Option B: Heap Sort, as it meets the criteria of O(n log n) in the worst case and is not stable.