# 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;
}
}

• max heapify seems to run in O(n) and you do it O(n) times resulting in O(n^2), the cause is the double recursion. you should only need to recurse down one branch – ratchet freak Apr 22 '16 at 12:02
• Your heapsort sorts [60, 1, 80, 64, 9, 94, 23, 88, 77, 98] incorrectly. – coderodde Apr 22 '16 at 12:16
• @coderodde ooh yeah it did mistake [1, 9, 23, 60, 64, 77, 80, 88, 98, 94], Thanks! i will check on it. – Kanagavelu Sugumar Apr 22 '16 at 12:19

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

1. swap
2. maxHeapify for maintaining the max-heap invariant; the topmost invocation must run in $\mathcal{O}(\log n)$.
3. buildMaxHeap, Introduction to Algorithms has a funky proof that this runs in linear time. Since, it is called only once, linear time is OK.
4. 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.

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 << 1) + 1;
final int rightChildIndex = leftChildIndex + 1;

int largestIndex;

if (leftChildIndex < heapSize
&& array[leftChildIndex] > array[index]) {
largestIndex = leftChildIndex;
} else {
largestIndex = index;
}

if (rightChildIndex < heapSize
&& array[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.