Różne czasy sortowań

Juz ostatnie dzisiaj pytanko..
Mierze czasy 3 sortowań :my_heapsort, sort_heap, i qsort

Pod windowsem (Dev-C++) dostaje takie wyniki:

TEST DLA 500000 LICZB
my_heapsort: 1.65
std::sort_heap: 1.04
Qsort: 5.72
TEST DLA 1000000 LICZB
my_heapsort: 5.38
std::sort_heap: 3.9
Qsort: 63.99
TEST DLA 1500000 LICZB
my_heapsort: 15.04
std::sort_heap: 13.74
Qsort: nie wiem, bo sie nie kończy ;)

a na serwerze uczelni (SunOS) takie:

TEST DLA 500000 LICZB
my_heapsort: 4.87
std::sort_heap: 2.55
Qsort: 0.1
TEST DLA 1000000 LICZB
my_heapsort: 16.16
std::sort_heap: 11.28
Qsort: 0.32
TEST DLA 1500000 LICZB
my_heapsort: 33.85
std::sort_heap: 24.54
Qsort: 0.65

Skad takie rozbierzności? Które wyniki mogą byc poprawne?

Zamieszcze kod my_heap:

using namespace std;
template<class RandomAccessIterator, class P>
void my_heapsort(RandomAccessIterator First, RandomAccessIterator Last, P Comp)
{
       typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
       value_type tmp;
       int size=Last-First;
       for (int i = size/2; i > 0; i--)
        {
                fix_heap(First, size,i, Comp);
        }
        
        while(size>=1)
        {
        
        tmp=*(First);
        *(First)=*(Last);
        *(Last)=tmp;
        --Last;
        --size;
        fix_heap(First,size, 0, Comp);
        }
}
  
          
template<class RandomAccessIterator, class P>
void fix_heap(RandomAccessIterator _first, unsigned int size, unsigned int node, P Comp)
{
        int left = node*2;
        int right = left+1;
        int max = node;
        if (size > left && Comp(*(_first+max), *(_first+left)))
                max = left;
        if ( right < size && Comp(*(_first+max),*(_first+right)) )
                max = right;
        if ( max != node ) {
            typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
                value_type tmp;
                
                tmp=*(_first+node); 
                *(_first+node)=*(_first+max);
                *(_first+max)=tmp;
                fix_heap(_first, size, max, Comp);
        }
}

Jakby ktoś wiedzial jak to jeszcze przyspieszyć, bede ogromnie wdzięczny.

Jeżeli to jest qsort z stdlib, to powinien być najszybszy z nich wszystkich. Albo jest jakiś błąd u ciebie, albo jakąś zepsutą wersję Dev-C++ masz.

Jak chcesz mieć jeszcze szybszy niż sort_heap oraz my_heap to sądzę, że zwykłe std:sort wykorzystujące introsort dałoby najlepsze wyniki.

Przyczyn może być wiele.

• sortujesz różne zestawy liczb
• test przeprowadzasz raz (a powinieneiś raczej uśrednić czasy sortowania dla różnych serii danych)
• czas na desktopie mierzysz inaczej niż na serwerze (np. na serwerze mierzysz czas życia wątku, a nie faktyczny czas sortowania)