how to implment heapsort with specific instructions. It must be a bottom-up approach, therefore, when building the heap it must be bottom up, when removing the maxheap value in the node, it must search through the array from bottom-up and not search from bottom down. It must have methods to trace the values

public static void sort(int input[], int traceStep)

{

}

and a regular sorting method

public static void sort(int input[])

{

}

Bottom-up heapsort was announced as beating quicksort (with median-of-three pivot selection) on arrays of size 216000.11 This version of heapsort keeps the linear-time heap-building phase, but changes the second phase, as follows. Ordinary heapsort extracts the top of the heap, a[0], and fills the gap it leaves with a[end], then sifts this latter element down the heap; but this element comes from the lowest level of the heap, meaning it is one of the smallest elements in the heap, so the sift down will likely take many steps to move it back down. Bottom-up heapsort instead finds the element to fill the gap, by tracing a path of maximum children down the heap as before, but then sifts that element up the heap, which is likely to take fewer steps.12] function leafSearch (a, i, end) is while iLeftchild(j) s end do (Determine which of j's children is the greater) if iRightChi ld (j) end and a[iRightChild (j)] > a[iLeftChild(j)] then j iRightChild (j) else j iLeftchild(j) return j The return value of the leafsearch is used in a replacement for the siftDown routine:12] procedure siftDown ( a, i, is end ) leafsearch(a, i, end) while a[i] > alj do j ? |Parent (j) while j > i do swap x, aliParent (j)1 j iParent (j) Bottom-up heapsort requires only 1.5 n log n + O(n) comparisons in the worst case and n logn + O(1) on average. A 2008 re-evaluation of this algorithm showed it to be no faster than ordinary heapsort, though, presumably because modern branch prediction nullifies the cost of the comparisons that bottom-up heapsort manages to avoid. 13)