heapsort - implementation's complexity

Question

I wrote heapsort (Cormen). Algorithm is sorting correctly but complexity is greater than expected.

void heap_sort(int tab[], int length)
{
    build_max_heap(tab, length);
    int heap_size = length;
    for (int i = length-1; i > 1; i--)
    {
        int tmp = tab[1];
        tab[1] = tab[i];
        tab[i] = tmp;
        heap_size--;
        max_heapify(tab, 1, heap_size);
    }
}

void max_heapify (int tab[], int i, int length)
{
    int largest;
    int l = i * 2;
    int r = i * 2 + 1;
    if (l < length and tab[l] > tab[i])
        largest = l;
    else
        largest = i;
    if (r < length and tab[r] > tab[largest])
        largest = r;
    if (largest != i)
    {
        int tmp = tab[i];
        tab[i] = tab[largest];
        tab[largest] = tmp;
        max_heapify(tab, largest, length);
    }
}

void build_max_heap(int tab[], int length)
{
    for (int i = length/2; i >= 1; i--)
        max_heapify(tab, i, length);
}

For 15000000 numbers generated by rand() it lasted longer than sorting with Shell sort in this implementation:

void shell_sort (int tab[], int length)
{
    int x = 2;
    int q;
    do
    {
        x*=2;
        q=2*(length/x) + 1;
        for(int i = q, val, j; i < length; i++)
        {
            val = tab[i];
            for(j = i - q ; j >= 0 and tab[j] > val; j-=q)
            {
                tab[j + q] = tab[j];
            }
            tab[j + q] = val;
        }
    }while (q > 1);
}

Test:

HEAPSORT
Time for 1000000 elements: 0.336 s
Time for 2000000 elements: 0.732 s
Time for 3000000 elements: 1.142 s
Time for 4000000 elements: 1.595 s
Time for 5000000 elements: 2.034 s
Time for 6000000 elements: 2.513 s
Time for 7000000 elements: 3.023 s
Time for 8000000 elements: 3.51 s
Time for 9000000 elements: 4.02 s
Time for 10000000 elements: 4.558 s
Time for 11000000 elements: 5.095 s
Time for 12000000 elements: 5.595 s
Time for 13000000 elements: 6.183 s
Time for 14000000 elements: 6.7 s
Time for 15000000 elements: 7.367 s

SHELLSORT
Time for 1000000 elements: 0.343 s
Time for 2000000 elements: 0.779 s
Time for 3000000 elements: 1.182 s
Time for 4000000 elements: 1.654 s
Time for 5000000 elements: 2.218 s
Time for 6000000 elements: 2.672 s
Time for 7000000 elements: 3.34 s
Time for 8000000 elements: 3.778 s
Time for 9000000 elements: 4.297 s
Time for 10000000 elements: 4.903 s
Time for 11000000 elements: 4.872 s
Time for 12000000 elements: 5.514 s
Time for 13000000 elements: 6.29 s
Time for 14000000 elements: 6.994 s
Time for 15000000 elements: 7.121 s

I repeated the test many times. What's wrong with the algorythm?

Answer 1

First note, big-O and raw performance have a complicated relationship. In the case of heapsort, poor memory locality will cause it to scale worse on computers than big-O would suggest. By contrast shell sort is only very slightly worse than O(n log(n)) and most of its passes have decent memory locality.

I'm therefore not surprised that they are comparable.

That said, you could try turning max_heapify from a recursive function into a loop. That may avoid a certain amount of stack manipulation.