Question

Why is heap sort preferred over merge sort for introsort implementation?

(a) Because heap sort is faster

(b) Because heap sort requires less space

(c) Because heap sort is easy to implement

(d) Because heap sort is easy to understand

I had been asked this question by my college director while I was bunking the class.

Query is from Sorting in division Sorting of Data Structures & Algorithms II

Answer 1

Correct answer is (b) Because heap sort requires less space

Best explanation: Both heap sort and merge sort have the same time complexity. But heap sort is an in-place sorting algorithm whereas merge sort requires O(n) auxiliary space which makes heap sort a more preferable option.