Question #52154

Which of the following sorting algorithms with a time complexity of O(n log(n)) even in the worst case?

Heapsort

Mergesort

Binary

Options A and B

Heapsort

Mergesort

Binary

Options A and B

Expert's answer

by extracting the largest element and moving that to the sorted region.

Heapsortalso competes with merge sort, which has the same time bounds. Merge sort

requires Ω(n) auxiliary space, but heapsort requires only a constant amount.

Heapsort typically runs faster in practice on machines with small or slow data

caches. On the other hand, merge sort has several advantages over heapsort:

## Comments

## Leave a comment