Heap Sort implementation time complexity
correctNode() looks like an (algorithmic) code-smell: its not needed. The only routines required to implement heap sort are:


swap
maxHeapify for maintaining the max-heap invariant; the topmost invocation must run in \$\mathcal{O}(\log n)\$.
buildMaxHeap, Introduction to Algorithms has a funky proof that this runs in linear time. Since, it is called only once, linear time is OK.
The actual heap sort routine: builds the max heap and pops in order until sorted.


The length argument of your heap sort is not needed. You can alwasy ask array.length.

I had this in mind:

public static void sort(final int[] array) {
    buildMaxHeap(array);
    int heapSize = array.length;

    for (int i = array.length - 1; i &gt; 0; --i) {
        swap(array, 0, i);
        maxHeapify(array, 0, --heapSize);
    }
}

private static void buildMaxHeap(final int[] array) {
    for (int i = array.length / 2; i &gt;= 0; --i) {
        maxHeapify(array, i, array.length);
    }
}

private static void maxHeapify(final int[] array, 
                               final int index,
                               final int heapSize) {
    final int leftChildIndex = (index &lt;&lt; 1) + 1;
    final int rightChildIndex = leftChildIndex + 1;

    int largestIndex;

    if (leftChildIndex &lt; heapSize 
            &amp;&amp; array[leftChildIndex] &gt; array[index]) {
        largestIndex = leftChildIndex;
    } else {
        largestIndex = index;
    }

    if (rightChildIndex &lt; heapSize
            &amp;&amp; array[rightChildIndex] &gt; array[largestIndex]) {
        largestIndex = rightChildIndex;
    }

    if (largestIndex != index) {
        swap(array, largestIndex, index);
        maxHeapify(array, largestIndex, heapSize);
    }
}

private static void swap(final int[] array, 
                         final int index1, 
                         final int index2) {
    final int tmp = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}


Hope that helps.