time into the correct position in the sorted arrayheapsort(array aint nheapify( ,nforj -swap [ and [jbubbledown( , , - it is clear from the swap step that the order of identical items can easily be reversedso there is no way to render the heapsort algorithm stable the average and worst-case time complexities of the entire heapsort algorithm are given by the sum of two complexity functionsfirst that of heapify rearranging the original unsorted array into heap tree which is ( )and then that of making the sorted array out of the heap tree which is (nlog ncoming from the (nbubble-downs each of which has (log ncomplexity thus the overall average and worst-case complexities are both (nlog )and we now have sorting algorithm that achieves the theoretical best worst-case time complexity using more sophisticated priority queuessuch as binomial or fibonacci heapscannot improve on this because they have the same delete time complexity useful feature of heapsort is that if only the largest items need to be found and sortedrather than all nthe complexity of the second stage is only (mlog )which can easily be less than (nand thus render the whole algorithm only ( divide and conquer algorithms all the sorting algorithms considered so far work on the whole set of items together insteaddivide and conquer algorithms recursively split the sorting problem into more manageable sub-problems the idea is that it will usually be easier to sort many smaller collections of items than one big oneand sorting single items is trivial so we repeatedly split the given collection into two smaller parts until we reach the 'base caseof one-item collectionswhich require no effort to sortand then merge them back together again there are two main approaches for doing thisassuming we are working on an array of size with entries [ ], [ - ]then the obvious approach is to simply split the set of indices that iswe split the array at item / and consider the two sub-arrays [ ], [( - )/ and [( + )/ ], [ - this method has the advantage that the splitting of the collection into two collections of equal (or nearly equalsize at each stage is easy howeverthe two sorted arrays that result from each split have to be merged together carefully to maintain the ordering this is the underlying idea for sorting algorithm called mergesort another approach would be to split the array in such way thatat each stageall the items in the first collection are no bigger than all the items in the second collection the splitting here is obviously more complexbut all we have to do to put the pieces back together again at each stage is to take the first sorted array followed by the second sorted array this is the underlying idea for sorting algorithm called quicksort we shall now look in detail at how these two approaches work in practice