fig binary heap of height similarlythe other like terms simplify so we end up with the following formula for - - ( - - (nwhere nodes in the last step of the simplification above we have the sum of the first - powers of also known as the sum of geometric sequence this sum is equal to raised to the powerminus one this can be proven with simple proof by induction sowe have just proved that version of phase is (nphase ii is still ( log nso the overall complexity of heap sort is ( log nconsider binary heap of height (fig in such heapusing the sift down method the first sifting occurs at height in the tree where we have four nodes that may travel down one level in the tree at height we have two nodes that may travel down two levels finallythe root node may travel down three levels we have the following sum of maximum path lengths + + + + + + comparison to other sorting algorithms the heapsort algorithm operates in ( log ntimethe same complexity as the quicksort algorithm key difference is in the movement of individual values in quicksortvalues are always moved toward their final location heapsort moves values first to form heapthen moves them again to arrive at their final location this copy belongs to 'acha