Select all the statements below which are TRUE Heapsort and

Select all the statements below which are TRUE: Heapsort and Merge sort are asymptotically optimal comparison sorts. Any sorting algorithm has running time Theta (n) since it has to traverse the sequence of elements. Quick sort is not a comparison sort because it calls the PARTITION function. Insertion sort is an asymptotically optimal comparison sort. Bucket sort is not a comparison sort. Any comparison sort algorithm requires Ohm (nlgn) comparisons in the worst case.

Solution

Statement :

Heap sort and merge sort are asymptotically optimal comparison sorts.

Mergesort and heapsort are comparison sorts .

These perform O(n log n) comparisons, so they are asymptotically optimal in this sense.

The statement is true.