C++ "sort"

[FlatAssembler]

Anyway, I've implemented a HybridSort algorithm, which behaves like QuickSort when the array appears to be randomly shuffled, and it behaves like MergeSort when the array appears to be nearly-sorted:

Code:

;HybridSort algoritam - kombinacija QuickSort algoritma i MergeSort algoritma.
AsmStart
    ispisPoruka=1
    macro staviIntNaSistemskiStog x
    {
        sub esp,4
        fld dword [x]
        fistp dword [esp]
    }
    macro staviPokazivacNaSistemskiStog x
    {
        sub esp,4
        lea ebx,[x]
        mov [esp],ebx
    }
    macro staviStringNaSistemskiStog x
    {
        sub esp,4
        mov dword [esp],x
    }
    format PE console
    entry start

    include 'win32a.inc'

    section '.text' code executable
    start:
if ispisPoruka=1
    jmp velicinaUnosa$
        velicinaUnosa db "Unesite koliko cete brojeva unijeti.",10,0
    velicinaUnosa$:
    staviStringNaSistemskiStog velicinaUnosa
    call [printf]
end if
    staviPokazivacNaSistemskiStog n
    jmp znakZaFloat$
        znakZaFloat db "%f",0
    znakZaFloat$:
    staviStringNaSistemskiStog znakZaFloat
    call [scanf]
    if ispisPoruka=1
        jmp pitajZaUnos$
            pitajZaUnos db "Unesite te brojeve:",10,0
        pitajZaUnos$:
        staviStringNaSistemskiStog pitajZaUnos
        call [printf]
    end if
AsmEnd
i:=0
brojac:=0
vrhStoga:=0
While i<n
    pokazivac:=4*i
    AsmStart
        fld dword [pokazivac]
        fistp dword [pokazivac]
        lea ebx,[original]
        add ebx,[pokazivac]
        staviPokazivacNaSistemskiStog ebx
        staviStringNaSistemskiStog znakZaFloat
        call [scanf]
    AsmEnd
    i:=i+1
EndWhile
AsmStart
    call [clock]
    mov [procesorskoVrijeme],eax
AsmEnd
razvrstanost:=0
i:=0
While i<n-1
    razvrstanost:=razvrstanost+(original(i)<original(i+1))
    i:=i+1
    brojac:=brojac+1
EndWhile
razvrstanost:=razvrstanost/((n-1)/2)-1
AsmStart
    if ispisPoruka=1
        jmp izvjesceORazvrstanosti$
            izvjesceORazvrstanosti db "Razvrstanost pocetnog niza iznosi: %f",10,0
        izvjesceORazvrstanosti$:
        fld dword [razvrstanost]
        fstp qword [esp]
        staviStringNaSistemskiStog izvjesceORazvrstanosti
        call [printf]
    end if
AsmEnd
i:=2
While i<7 | i=7
    razvrstanostNa(i):=pow(abs(razvrstanost),i)
    If razvrstanost=0
        razvrstanostNa(i):=0
    EndIf
    If mod(i,2)=1 & razvrstanost<0
        razvrstanostNa(i):=-razvrstanostNa(i)
    EndIf
    i:=i+1
EndWhile
polinomPodApsolutnom:=2.38854*razvrstanostNa(7)-0.284258*razvrstanostNa(6)-1.87104*razvrstanostNa(5)+0.372637*razvrstanostNa(4)+0.167242*razvrstanostNa(3)-0.0884977*razvrstanostNa(2)+0.315119*razvrstanost
eNaKoju:=(ln(n)+ln(ln(n)))*1.05+(ln(n)-ln(ln(n)))*0.83*abs(polinomPodApsolutnom)
ocekivaniBrojUsporedbi:=exp(eNaKoju)
ocekivanoOdMergeSorta:=2*n*ln(n)/ln(2)
AsmStart
    if ispisPoruka=1
        jmp ispisOTomeStoOcekujemo$
            ispisOTomeStoOcekujemo db "Od QuickSorta ocekujemo %f usporedbi, a od MergeSorta ocekujemo %f usporedbi.",10,0
        ispisOTomeStoOcekujemo$:
        fld dword [ocekivanoOdMergeSorta]
        fstp qword [esp+8]
        fld dword [ocekivaniBrojUsporedbi]
        fstp qword [esp]
        staviStringNaSistemskiStog ispisOTomeStoOcekujemo
        call [printf]
    end if
AsmEnd
najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac:=1
pomocniBrojac:=0
If razvrstanost=1
    AsmStart
        if ispisPoruka=1
            jmp nizJeVecRazvrstan$
                nizJeVecRazvrstan db "Niz je vec poredan, ne radimo nista.",10,0
            nizJeVecRazvrstan$:
            invoke printf,nizJeVecRazvrstan
        end if
    AsmEnd
ElseIf razvrstanost=(-1)
    AsmStart
        if ispisPoruka=1
            jmp nizJeObrnutoRazvrstan$
                nizJeObrnutoRazvrstan db "Niz je obrnuto poredan.",10,0
            nizJeObrnutoRazvrstan$:
            invoke printf,nizJeObrnutoRazvrstan
        end if
    AsmEnd
    i:=0
    While i<n
        pomocni(i):=original(n-i-1)
        i:=i+1
        brojac:=brojac+1
    EndWhile
    i:=0
    While i<n
        original(i):=pomocni(i)
        i:=i+1
    EndWhile
ElseIf ocekivaniBrojUsporedbi<ocekivanoOdMergeSorta
    AsmStart
        if ispisPoruka=1
            jmp radimoQuickSort$
                radimoQuickSort db "Primijenit cemo QuickSort algoritam.",10,0
            radimoQuickSort$:
            invoke printf,radimoQuickSort
        end if
    AsmEnd
    vrhStoga:=vrhStoga+1
    stogSDonjimGranicama(vrhStoga):=0
    stogSGornjimGranicama(vrhStoga):=n
    While vrhStoga>0
        gornjaGranica:=stogSGornjimGranicama(vrhStoga)
        donjaGranica:=stogSDonjimGranicama(vrhStoga)
        vrhStoga:=vrhStoga-1
        gdjeJePivot:=donjaGranica
        i:=donjaGranica+1
        While i<gornjaGranica
            If original(i)<original(donjaGranica)
                gdjeJePivot:=gdjeJePivot+1
            EndIf
            i:=i++
        EndWhile
        staviManje:=donjaGranica
        staviVece:=gdjeJePivot+1
        pomocni(gdjeJePivot):=original(donjaGranica)
        i:=donjaGranica+1
        While i<gornjaGranica
            If original(i)<original(donjaGranica)
                pomocni(staviManje):=original(i)
                staviManje:=staviManje+1
            Else
                pomocni(staviVece):=original(i)
                staviVece:=staviVece+1
            EndIf
            pomocniBrojac:=pomocniBrojac+1
            If pomocniBrojac=najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac
                brojac:=brojac+pomocniBrojac
                pomocniBrojac:=0
            EndIf
            i:=i+1
        EndWhile
        i:=donjaGranica
        While i<gornjaGranica
            original(i):=pomocni(i)
            i:=i+1
        EndWhile
        If gdjeJePivot<gornjaGranica-1
            vrhStoga:=vrhStoga+1
            stogSDonjimGranicama(vrhStoga):=gdjeJePivot+1
            stogSGornjimGranicama(vrhStoga):=gornjaGranica
        EndIf
        If gdjeJePivot>donjaGranica+1
            vrhStoga:=vrhStoga+1
            stogSDonjimGranicama(vrhStoga):=donjaGranica
            stogSGornjimGranicama(vrhStoga):=gdjeJePivot
        EndIf
        testZaPreljev:=brojac+najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac ;Potrebna je posebna varijabla za to jer FPU interno radi s 80-bitnim brojevima, a CPU s 32-bitnim.
        If not(testZaPreljev>brojac)
            najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac:=najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac*2
            AsmStart
                if ispisPoruka=1
                    jmp izvjesceOpreljevu$
                        izvjesceOpreljevu db "Upozorenje: Brojac mozda nece sadrzavati tocan rezultat, dogodio se preljev na %d. iteraciji."
                        db " Najveca ocekivana pogreska za ovaj preljev je %d krivo prebrojanih izvrsavanja unutarnje petlje.",10,0
                    izvjesceOpreljevu$:
                    fld dword [n]
                    fld dword [najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac]
                    fsubp
                    fabs
                    fistp dword [esp+4]
                    fld dword [brojac]
                    fistp dword [esp]
                    invoke printf,izvjesceOpreljevu
                end if      
            AsmEnd
        EndIf
    EndWhile
Else
    AsmStart
        if ispisPoruka=1
            jmp radimoMergeSort$
                radimoMergeSort db "Primijenit cemo MergeSort algoritam.",10,0
            radimoMergeSort$:
            invoke printf,radimoMergeSort
        end if
    AsmEnd
    vrhStoga:=vrhStoga+1
    stogSDonjimGranicama(vrhStoga):=0
    stogSGornjimGranicama(vrhStoga):=n
    stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=0
    While vrhStoga>0
        gornjaGranica:=stogSGornjimGranicama(vrhStoga)
        donjaGranica:=stogSDonjimGranicama(vrhStoga)
        trebaLiSpajatiIliRazdvajati:=stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga)
        vrhStoga:=vrhStoga-1
        sredinaNiza:=(donjaGranica+gornjaGranica)/2
        sredinaNiza:=sredinaNiza-mod(sredinaNiza,1)
        If trebaLiSpajatiIliRazdvajati=0
            If gornjaGranica-donjaGranica>1
                vrhStoga:=vrhStoga+1
                stogSDonjimGranicama(vrhStoga):=donjaGranica
                stogSGornjimGranicama(vrhStoga):=gornjaGranica
                stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=1
                vrhStoga:=vrhStoga+1
                stogSDonjimGranicama(vrhStoga):=donjaGranica
                stogSGornjimGranicama(vrhStoga):=sredinaNiza
                stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=0
                vrhStoga:=vrhStoga+1
                stogSDonjimGranicama(vrhStoga):=sredinaNiza
                stogSGornjimGranicama(vrhStoga):=gornjaGranica
                stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove(vrhStoga):=0
            EndIf
        Else
            i:=donjaGranica
            gdjeSmoUPrvomNizu:=donjaGranica
            gdjeSmoUDrugomNizu:=sredinaNiza
            While i<gornjaGranica
                If (gdjeSmoUPrvomNizu=sredinaNiza | original(gdjeSmoUDrugomNizu)<original(gdjeSmoUPrvomNizu)) & gdjeSmoUDrugomNizu<gornjaGranica
                    pomocni(i):=original(gdjeSmoUDrugomNizu)
                    gdjeSmoUDrugomNizu:=gdjeSmoUDrugomNizu+1
                Else
                    pomocni(i):=original(gdjeSmoUPrvomNizu)
                    gdjeSmoUPrvomNizu:=gdjeSmoUPrvomNizu+1
                EndIf
                i:=i+1
                brojac:=brojac+1
            EndWhile
            i:=donjaGranica
            While i<gornjaGranica
                original(i):=pomocni(i)
                brojac:=brojac+1
                i:=i+1
            EndWhile
        EndIf
    EndWhile
EndIf
AsmStart
    call [clock]
    sub eax,[procesorskoVrijeme]
    mov [procesorskoVrijeme],eax
if ispisPoruka=1
    jmp sortiraniNizJe$
        sortiraniNizJe db "Sortirani niz je:",10,0
    sortiraniNizJe$:
    staviStringNaSistemskiStog sortiraniNizJe
    call [printf]
end if
AsmEnd
i:=0
While i<n
    pokazivac:=4*i
    AsmStart
        lea ebx,[original]
        fld dword [pokazivac]
        fistp dword [pokazivac]
        add ebx,[pokazivac]
        fld dword [ebx]
        fstp qword [esp]
        staviStringNaSistemskiStog znakZaFloatPlusNoviRedPlusNulZnak
        call [printf]
    AsmEnd
    i:=i+1
EndWhile
AsmStart
if ispisPoruka=1
    staviIntNaSistemskiStog brojac
    staviStringNaSistemskiStog unutrasnjaPetljaString
    call [printf]
AsmEnd
    brojac:=n*ln(n)/ln(2)
AsmStart
    fld dword [brojac]
    fstp qword [esp]
    staviStringNaSistemskiStog slozenostString
    call [printf]
    push dword [procesorskoVrijeme]
    invoke printf,sortiranjeJeTrajalo
    invoke system,_pause
end if
invoke exit,0

_pause db "PAUSE",0
znakZaCijeliBrojBroj db "%d",0
znakZaNoviRedPlusNulZnak db 10,0
znakZaFloatPlusNoviRedPlusNulZnak db "%f",10,0
unutrasnjaPetljaString db "Unutrasnja petlja izvrsila se %d puta.",10,0
slozenostString db "Ocekivani broj ponavljanja te petlje, po formuli n*log2(n), bio bi %.1f.",10,0
sortiranjeJeTrajalo db "Sortiranje je trajalo %d milisekundi.",10,0

section '.rdata' readable writable
    original:
        repeat 32768
            dd 0
        end repeat
    n dd ?
    result dd ?
    brojac dd ?
    pokazivac dd ?
    i dd ?
    stogSDonjimGranicama:
        repeat 32768
            dd 0
        end repeat
    stogSGornjimGranicama:
        repeat 32768
            dd 0
        end repeat
    pomocni:
        repeat 32768
            dd 0
        end repeat
    vrhStoga dd ?
    donjaGranica dd ?
    gornjaGranica dd ?
    staviVece dd ?
    staviManje dd ?
    gdjeJePivot dd ?
    procesorskoVrijeme dd ?
    razvrstanost dd ?
    razvrstanostNa dd 8 DUP(?)
    polinomPodApsolutnom dd ?
    eNaKoju dd ?
    ocekivaniBrojUsporedbi dd ?
    ocekivanoOdMergeSorta dd ?
    najmanjiCijeliBrojKojiSeMozeDodatiNaBrojac dd ?
    pomocniBrojac dd ?
    testZaPreljev dd ?
    gdjeSmoUDrugomNizu dd ?
    gdjeSmoUPrvomNizu dd ?
    trebaLiSpajatiIliRazdvajati dd ?
    sredinaNiza dd ?
    stogSPodacimaTrebaLiPetljaRazdvajatiIliSpajatiNizove:
        repeat 32768
            dd 0
        end repeat


section '.idata' data readable import
    library msvcrt,'msvcrt.dll'
        import msvcrt,printf,'printf',system,'system',exit,'exit',scanf,'scanf',clock,'clock'
AsmEnd

The 32-bit Windows executable is available here. I must say I've expected it to be a lot more efficient than it actually is. I've expected it to be comparable with IntroSort (used in C++ "sort" directive), however, it appears to be a few times slower than IntroSort: