Heap Sort implementation time complexity

I have implemented Heap sort, but i think the time complexity is more than (nlogn).
Could anyone explain me; what is wrong in my code which makes more time complexity.

I will be glad if the answer is in terms of algorithm time complexity based.

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] array = { 5, 6, 10, 3, 9, 2, 12, 1, 8, 7 };
        maxHeapSort(array, array.length);
        System.out.println(Arrays.toString(array));
        System.out.println("\n\n");
    }

    private static void maxHeapSort(int[] array, int length) {
        for(int i = 1; i < length; i++ ) {
            maxHeapify(array, 1, length-i);
            swap(array, 0, length-i);
        }
        //Working on last three indexes [which is 0,1,2]
        correctNode(array, 1, 3);
        swap(array, 0, 2);
        correctNode(array, 1, 2);
        swap(array, 0, 1);
    }

    private static void maxHeapify(int[] array, int nodeIndex, int length) {
        if(nodeIndex < length) {
            correctNode(array, nodeIndex, length);
            maxHeapify(array, 2 * nodeIndex, length);
            maxHeapify(array, (2 * nodeIndex)+1, length);
            correctNode(array, nodeIndex, length);
        }
    }

    private static void correctNode(int[] array, int index, int length) {
        int rootIndex = index - 1;
        int leftIndex = (2 * index) - 1;
        int rightIndex = ((2 * index) + 1) - 1;
        if(leftIndex < length && array[rootIndex] < array[leftIndex]) {
            swap(array, rootIndex, leftIndex);
        }

        if(rightIndex < length && array[rootIndex] < array[rightIndex]) {
            swap(array, rootIndex, rightIndex);
        }
    }

    private static void swap(int[] array, int m, int n){
        int temp = array[m];
        array[m] = array[n];
        array[n] = temp;
    }
}

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 > 0; --i) {
        swap(array, 0, i);
        maxHeapify(array, 0, --heapSize);
    }
}

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

private static void maxHeapify(final int[] array, 
                               final int index,
                               final int heapSize) {
    final int leftChildIndex = (index  array[index]) {
        largestIndex = leftChildIndex;
    } else {
        largestIndex = index;
    }

    if (rightChildIndex  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.

StackExchange Code Review Q#126428, answer score: 2