wrong heap sort algorithm

[FishingKingczj]

https://github.com/mandliya/algorithms_and_data_structures/blob/master/include/heap_sort.h
I think there are two logic errors in this file.

First in line 31：

swpIdx = root;

In fact root has not changed in the while body, so this statement is meaningless actually, the while loop always stop at the second time.
It should be write like this:

root = swpIdx;

Second, although this algorithm can finish sorting, it is not a strictly correct heap sort.
For in line 53, the while body.

//heapify the list
__heapify(list, 0, size-1);

int high = size - 1;
while ( high > 0 ) {
    algo::swap(list[high], list[0]);
    --high;
    __heapify(list, 0, high);
}

Correct heap sort call function “heapify” once and function “sift_down” n - 1 times.
So in the while body should call “sift_down”, but not “heapify”.
It leads to the time complexity of the algorithm is O(n^2) but not O(nlogn) for strict heap sort.

[yuzhouChen]

Can I try to fix it

[navdeepkk]

#42 Please approve and merge this.
@mandliya

[Shakileash5]

@FishingKingczj the errors are fixed

[Shakileash5]

https://github.com/mandliya/algorithms_and_data_structures/blob/master/include/heap_sort.h
I think there are two logic errors in this file.

First in line 31：

swpIdx = root;

In fact root has not changed in the while body, so this statement is meaningless actually, the while loop always stop at the second time.
It should be write like this:

root = swpIdx;

Second, although this algorithm can finish sorting, it is not a strictly correct heap sort.
For in line 53, the while body.

//heapify the list
__heapify(list, 0, size-1);

int high = size - 1;
while ( high > 0 ) {
    algo::swap(list[high], list[0]);
    --high;
    __heapify(list, 0, high);
}

Correct heap sort call function “heapify” once and function “sift_down” n - 1 times.
So in the while body should call “sift_down”, but not “heapify”.
It leads to the time complexity of the algorithm is O(n^2) but not O(nlogn) for strict heap sort.

both logics are fixed