Heapsort is one of the fastest sorting algorithms. The best and the worst cases for heapsort have the same $O(n\log(n))$ performance.
First, heapsort creates a heap from the data with the buildHeap function. The heap is organized in a linear array as follows. Every $i$-th element has two children: the $(2i)$-th element and the $(2i+1)$-th one. The biggest element of the array is placed on the top of the heap.
After the heap is built, the top element is swapped with the last one in the array; then the heap is rebuilt for the array with the size decreased by one. These operations repeat until the array size is bigger than one. Note that the array indexes have to start from one for this implementation to work correctly (that is why I use size+1 for the array size).
My implementation of heapsort is presented below. heapsort.cpp:
1#include <iostream>
2#include <cstdlib>
3#include <algorithm>
4
5template <typename T>
6void checkRootNode(T *array, size_t root, size_t size) {
7 size_t left = 2*root;
8 size_t right = 2*root + 1;
9 if (left < size && array[root] < array[left]) {
10 std::swap(array[root], array[left]);
11 checkRootNode(array, left, size);
12 }
13 if (right < size && array[root] < array[right]) {
14 std::swap(array[root], array[right]);
15 checkRootNode(array, right, size);
16 }
17}
18
19template <typename T>
20void buildHeap(T *array, size_t size) {
21 for (size_t i=size/2; i>0; --i) {
22 checkRootNode(array, i, size);
23 }
24}
25
26template <typename T>
27void heapSort(T *array, size_t size) {
28 while (size > 1) {
29 std::swap(array[1], array[size-1]);
30 checkRootNode(array, 1, --size);
31 }
32}
33
34template <typename T>
35void printArray(T *array, size_t size) {
36 for (size_t i=1; i < size; ++i) {
37 std::cout << array[i] << ' ';
38 }
39 std::cout << std::endl;
40}
41
42int main(void) {
43 size_t size = 23;
44 int *array = new int[size+1];
45
46 for (int i=1; i<size+1; ++i) {
47 array[i] = (100.0*rand())/RAND_MAX;
48 }
49
50 printArray(array, size);
51 buildHeap(array, size);
52 heapSort(array, size);
53 printArray(array, size);
54
55 delete [] array;
56
57 return 0;
58}
Results:
1[kenarius@cudasus]$ g++ heapsort.cpp
2[kenarius@cudasus]$ ./a.out
384 39 78 79 91 19 33 76 27 55 47 62 36 51 95 91 63 71 14 60 1 24
41 14 19 24 27 33 36 39 47 51 55 60 62 63 71 76 78 79 84 91 91 95