Answer to Question #52154 in Other Programming & Computer Science for irebami
Which of the following sorting algorithms with a time complexity of O(n log(n)) even in the worst case?
Options A and B
Heapsort and Mergesort sorting algorithms have inworth case complexity [img width=106,height=23]file:///C:/Users/sergiy.r/AppData/OICE_15_974FA576_32C1D314_6B/msohtmlclip1/01/clip_image002.png[/img]. Algorithm divides its input into asorted and an unsorted region, and it iteratively shrinks the unsorted region 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: