HybridSort of QuickSort and MergeSort

Question

I'll try to publish a paper about the programming language I've made (ArithmeticExpressionCompiler, short AEC) in Osječki Matematički List and, in order to demonstrate its usability for implementing algorithms, I've tried to implement a fast sorting algorithm in it.

The basic idea of my algorithm is that QuickSort works better when the array is randomly-shuffled, while MergeSort works better when the array is already nearly sorted. Here it goes:

Syntax GAS ;Neka ArithmeticExpressionCompiler ispisuje asemblerski kod kompatibilan s GNU Assemblerom, da bude kompatibilan s GCC-om. Po defaultu ispisuje kod kompatibilan s FlatAssemblerom (a FlatAssembler na Linuxu ne radi bas najbolje).
verboseMode ON ;Neka ArithmeticExpressionCompiler ispisuje vise komentara u asemblerski kod koji ispisuje (da bude laksi za citanje i debuggiranje).
AsmStart ;Neka GNU Assembler obavijesti linkera da je "hybrid_sort" naziv potprograma...
    .global hybrid_sort
    hybrid_sort:
AsmEnd
If gornja_granica-donja_granica<2 ;Ako je niz duljine manje od 2 (0 ili 1), znaci da je vec poredan, pa prekidamo izvodenje ovog potprograma.
    AsmStart ;Kako radimo izvan sekcija, mozemo jednostavno prekinuti izvodenje potprograma asemblerskom naredbom "ret" (inace bismo, da radimo u sekcijama, morali znati vrti li se program na 32-bitnom ili 64-bitnom Linuxu).
        ret
    AsmEnd 
EndIf
razvrstanost:=0
i:=donja_granica
While i < gornja_granica - 1
    razvrstanost:=razvrstanost+(originalni_niz[i]<originalni_niz[i+1])
    i:=i+1
EndWhile
razvrstanost:=razvrstanost/((gornja_granica-donja_granica-1)/2)-1
i:=2
While i<7 | i=7 
    razvrstanost_na_potenciju[i] := pow(abs(razvrstanost), i) ;"pow(x,y)" je u AEC-u samo sintaksni secer za "exp(ln(x)*y)", i to vraca NaN za x=0 ili x<0. Nema ocitog nacina da se "pow(x,y)" prevede na asemblerski.
    razvrstanost_na_potenciju[i] := (razvrstanost=0) ? 0 : (mod(i,2)=1 & razvrstanost<0) ? (-razvrstanost_na_potenciju[i]) : razvrstanost_na_potenciju[i] ;C-ov i JavaScriptin uvjetni operator nekad zna znatno skratiti kod, zato sam ga ugradio i u svoj jezik.
    i:=i+1
EndWhile
;Formula koju je ispisao genetski algoritam za predvidanje koliko ce usporedbi QuickSort napraviti: https://github.com/FlatAssembler/ArithmeticExpressionCompiler/tree/master/QuickSort/Genetic_algorithm_for_deriving_the_formula
polinom_pod_apsolutnom := 2.38854*razvrstanost_na_potenciju[7] - 0.284258*razvrstanost_na_potenciju[6] - 1.87104*razvrstanost_na_potenciju[5] + 0.372637*razvrstanost_na_potenciju[4] + 0.167242*razvrstanost_na_potenciju[3] - 0.0884977*razvrstanost_na_potenciju[2] + 0.315119*razvrstanost
Eulerov_broj_na_koju_potenciju := (ln(gornja_granica - donja_granica) + ln(ln(gornja_granica - donja_granica))) * 1.05 + (ln(gornja_granica - donja_granica) - ln(ln(gornja_granica - donja_granica)) - ln(2)) * 0.9163 * abs(polinom_pod_apsolutnom)
koliko_usporedbi_ocekujemo_od_QuickSorta := exp(Eulerov_broj_na_koju_potenciju)
koliko_usporedbi_ocekujemo_od_MergeSorta := 2 * (gornja_granica - donja_granica) * ln(gornja_granica - donja_granica) / ln(2)
If razvrstanost=1 ;Ako je niz vec poredan.
    broj_vec_poredanih_podniza := broj_vec_poredanih_podniza + 1
    AsmStart
        ret
    AsmEnd
ElseIf razvrstanost = -1 ;Ako je niz obrnuto poredan...
    broj_obrnuto_poredanih_podniza := broj_obrnuto_poredanih_podniza + 1
    i:=donja_granica
    j:=gornja_granica-1
    While i<gornja_granica
        pomocni_niz[i] := originalni_niz[j]
        j := j - 1
        i := i + 1
    EndWhile
    i := donja_granica
    While i < gornja_granica
        originalni_niz[i] := pomocni_niz[i]
        i := i + 1
    EndWhile
    AsmStart
        ret
    AsmEnd
ElseIf koliko_usporedbi_ocekujemo_od_MergeSorta < koliko_usporedbi_ocekujemo_od_QuickSorta ;MergeSort algoritam (priblizno poredani podnizovi, za koje je MergeSort efikasniji od QuickSorta)...
    broj_pokretanja_MergeSorta := broj_pokretanja_MergeSorta + 1
    sredina_niza:=(gornja_granica+donja_granica)/2
    sredina_niza:=sredina_niza-mod(sredina_niza,1)
    vrh_stoga:=vrh_stoga+1 ;Zauzmi mjesta na stogu za rekurziju. Ne koristimo sistemski stog, kao sto koristi C++, nego koristimo vise globalnih polja kao stogove. Da koristimo sistemski stog, morali bismo znati pokrecemo li se na 32-bitnom Linuxu ili 64-bitnom Linuxu, jer oni nisu kompatibilni u tom pogledu.
    stog_s_donjim_granicama[vrh_stoga]:=donja_granica
    stog_s_gornjim_granicama[vrh_stoga]:=gornja_granica
    stog_sa_sredinama_niza[vrh_stoga]:=sredina_niza
    gornja_granica:=sredina_niza
    AsmStart
        call hybrid_sort
    AsmEnd
    donja_granica:=stog_s_donjim_granicama[vrh_stoga] ;Sad je rekurzija gotovo sigurno izmijenila sve globalne varijable koje nam trebaju ("donja_granica", "gornja_granica" i "sredina_niza"), ali zato imamo njihove stare vrijednosti na stogovima.
    gornja_granica:=stog_s_gornjim_granicama[vrh_stoga]
    sredina_niza:=stog_sa_sredinama_niza[vrh_stoga]
    donja_granica:=sredina_niza
    AsmStart
        call hybrid_sort
    AsmEnd
    donja_granica:=stog_s_donjim_granicama[vrh_stoga]
    gornja_granica:=stog_s_gornjim_granicama[vrh_stoga]
    sredina_niza:=stog_sa_sredinama_niza[vrh_stoga]
    ;Spajanje nizova originalni_niz[donja_granica..sredina_niza] i originalni_niz[sredina_niza..gornja_granica] u jedan niz...
    i:=donja_granica
    gdje_smo_u_prvom_nizu:=donja_granica
    gdje_smo_u_drugom_nizu:=sredina_niza
    While i<gornja_granica
        If (gdje_smo_u_prvom_nizu=sredina_niza | originalni_niz[gdje_smo_u_drugom_nizu]<originalni_niz[gdje_smo_u_prvom_nizu]) & gdje_smo_u_drugom_nizu<gornja_granica
            pomocni_niz[i]:=originalni_niz[gdje_smo_u_drugom_nizu]
            gdje_smo_u_drugom_nizu:=gdje_smo_u_drugom_nizu+1
        Else
            pomocni_niz[i]:=originalni_niz[gdje_smo_u_prvom_nizu]
            gdje_smo_u_prvom_nizu:=gdje_smo_u_prvom_nizu+1
        EndIf
        i:=i+1
    EndWhile
    i:=donja_granica
    While i<gornja_granica
        originalni_niz[i]:=pomocni_niz[i]
        i:=i+1
    EndWhile
    vrh_stoga:=vrh_stoga-1 ;Oslobodi mjesto na stogovima.
    AsmStart
        ret
    AsmEnd
Else ;QuickSort algoritam (nasumicno ispremjestani podnizovi)...
    broj_pokretanja_QuickSorta := broj_pokretanja_QuickSorta + 1
    ;Daljnji kod je priblizno prepisan s https://www.geeksforgeeks.org/quick-sort/
    pivot := originalni_niz[gornja_granica - 1]
    i := donja_granica - 1
    j := donja_granica
    While j < gornja_granica - 1
        If originalni_niz[j] < pivot
            i := i + 1
            pomocna_varijabla_za_zamijenu := originalni_niz[i]
            originalni_niz[i] := originalni_niz [j]
            originalni_niz[j] := pomocna_varijabla_za_zamijenu
        EndIf
        j:=j+1
    EndWhile
    pomocna_varijabla_za_zamijenu := originalni_niz[i + 1]
    originalni_niz[i + 1] := originalni_niz[gornja_granica - 1]
    originalni_niz[gornja_granica - 1] := pomocna_varijabla_za_zamijenu
    gdje_je_pivot := i + 1
    vrh_stoga := vrh_stoga + 1 ;Zauzmi mjesta na stogu za rekurziju (ne koristimo sistemski stog, kao sto koristi C++, nego koristimo vise globalnih polja kao stogove).
    stog_s_donjim_granicama[vrh_stoga] := donja_granica
    stog_s_gornjim_granicama[vrh_stoga] := gornja_granica
    stog_sa_sredinama_niza[vrh_stoga] := gdje_je_pivot
    gornja_granica := gdje_je_pivot
    AsmStart
        call hybrid_sort
    AsmEnd
    donja_granica := stog_s_donjim_granicama[vrh_stoga]
    gornja_granica := stog_s_gornjim_granicama[vrh_stoga]
    gdje_je_pivot := stog_sa_sredinama_niza[vrh_stoga]
    donja_granica := gdje_je_pivot
    AsmStart
        call hybrid_sort
    AsmEnd
    vrh_stoga := vrh_stoga - 1 ;Oslobodi mjesto na stogovima.
    AsmStart
        ret
    AsmEnd
EndIf
AsmStart ;Ovdje tok programa ne smije doci. Ako dode, pozovi debugger.
    call abort
AsmEnd

The assembly code that my compiler produces can be seen here. It can be assembled using GNU Assembler, however, you won't get an executable program from it. It's just a routine that expects to be called from an external program. An example of such a program is here:

/*
 * Dakle, ovo ce biti omotac oko "hybrid_sort.aec" napisan u C++-u.
 * "hybrid_sort.aec" sam po sebi nije program koji se moze pokrenuti,
 * i zato cemo od C++ compilera (u ovom slucaju, GCC-a) traziti da
 * napravi program unutar kojeg ce se "hybrid_sort.aec" moze pokrenuti,
 * i, po mogucnosti, koji ce olaksati da ga testiramo. Drugim rijecima,
 * ovo je program s kojim se "hybrid_sort.aec" moze staticki linkirati.
 * */
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <iterator>

namespace AEC { // Da se razlikuju AEC-ove varijable od C++-ovih.
extern "C" {    // Za GNU Linker (koji se dobije uz Linux i koristi ga GCC), AEC
// jezik je dijalekt C-a, a moj compiler je C compiler.
float result, originalni_niz[1 << 16], kopija_originalnog_niza[1 << 16],
    pomocni_niz[1 << 16], i, gdje_smo_u_prvom_nizu, gdje_smo_u_drugom_nizu,
    gornja_granica, donja_granica, sredina_niza,
    stog_sa_sredinama_niza[1 << 10], stog_s_donjim_granicama[1 << 10],
    stog_s_gornjim_granicama[1 << 10], vrh_stoga, pomocna_varijabla_za_zamijenu,
    gdje_je_pivot, j, pivot, koliko_usporedbi_ocekujemo_od_QuickSorta,
    koliko_usporedbi_ocekujemo_od_MergeSorta, razvrstanost,
    Eulerov_broj_na_koju_potenciju, polinom_pod_apsolutnom,
    razvrstanost_na_potenciju[8],
    broj_vec_poredanih_podniza = 0, broj_obrnuto_poredanih_podniza = 0,
    broj_pokretanja_MergeSorta = 0,
    broj_pokretanja_QuickSorta =
        0; // GNU Linker omogucuje da se varijable ne deklariraju ne samo u
           // razlicitim datotekama, nego i u razlicitim jezicima. Znaci, ne
           // moram traziti kako se, recimo, na 64-bitnom Linuxu deklariraju
           // globalne varijable na asemblerskom jeziku, jer GCC to vec zna.
void hybrid_sort(); //".global hybrid_sort" iz "hybrid_sort.aec". U C++-u ga
// morate deklarirati da biste ga mogli koristiti. C++ nije
// kao JavaScript ili AEC u tom pogledu, C++ pokusava pronaci
// krivo natipkana imena varijabli i funkcija vec za vrijeme
// compiliranja.
}
} // namespace AEC
const int n = 1 << 16;

int main() {
  std::cout << "sortedness\tsorted_array\treverse\tMergeSort\tQuickSort\n";
  for (int i = 0; i < n; i++)
    AEC::originalni_niz[i] = i;
  for (int i = 0; i <= n; i += 1 << 9) {
    std::sort(&AEC::originalni_niz[0], &AEC::originalni_niz[n]);
    if (i < (n / 2))
      std::reverse(&AEC::originalni_niz[0], &AEC::originalni_niz[n]);
    int broj_ispremjestanja = abs(i - (n / 2)) * 1.5;
    for (int j = 0; j < broj_ispremjestanja; j++)
      std::iter_swap(&AEC::originalni_niz[std::rand() % n],
                     &AEC::originalni_niz[std::rand() % n]);
    if (!(rand() % 100))
      std::random_shuffle(
          &AEC::originalni_niz[0],
          &AEC::originalni_niz[n]); // Ponekad namjesti da poredanost bude nula.
    if (!(rand() % 100))
      std::sort(&AEC::originalni_niz[0], &AEC::originalni_niz[n],
                [](float a, float b) -> bool {
                  return a > b;
                }); // Ponekad namjesti da poredanost bude 1. Za to sam koristio
                    // C++-ove lambda funkcije. Njih GCC podrzava jos od 2007, a
                    // komercijalni compileri jos od ranije. Nadam se da netko
                    // nece pokusati ukucati ovo u neki arhaican compiler.
    float razvrstanost = 0;
    for (int j = 0; j < n - 1; j++)
      razvrstanost += AEC::originalni_niz[j] < AEC::originalni_niz[j - 1];
    razvrstanost = razvrstanost / ((n - 1) / 2) - 1;
    std::copy_n(&AEC::originalni_niz[0], n, &AEC::kopija_originalnog_niza[0]);
    AEC::broj_vec_poredanih_podniza = 0;
    AEC::broj_obrnuto_poredanih_podniza = 0;
    AEC::broj_pokretanja_MergeSorta = 0;
    AEC::broj_pokretanja_QuickSorta = 0;
    AEC::gornja_granica = n;
    AEC::donja_granica = 0;
    AEC::vrh_stoga = -1;
    AEC::hybrid_sort();
    std::sort(&AEC::kopija_originalnog_niza[0],
              &AEC::kopija_originalnog_niza[n]);
    if (!std::equal(&AEC::originalni_niz[0], &AEC::originalni_niz[n],
                    &AEC::kopija_originalnog_niza[0])) {
      std::cerr << "C++-ov std::sort nije dobio isti rezultat za i=" << i << '!'
                << std::endl;
      return 1; // Javi operativnom sustavu da je doslo do pogreske.
    }
    std::cout << razvrstanost << '\t'
              << std::log(1 + AEC::broj_vec_poredanih_podniza)
              << '\t' // Broj vec poredanih podniza moze biti i nula (ako je,
                      // recimo, razvrstanost jednaka -1), a, kako logaritam od
                      // nula ne postoji, dodat cu jedinicu da se program ne rusi
                      // na nekim compilerima.
              << std::log(1 + AEC::broj_obrnuto_poredanih_podniza) << '\t'
              << std::log(1 + AEC::broj_pokretanja_MergeSorta) << '\t'
              << std::log(1 + AEC::broj_pokretanja_QuickSorta) << '\n';
  }
  std::flush(std::cout); // Obrisi meduspremnik prije no sto zavrsis program.
  return 0; // Javi operativnom sustavu da je program uspjesno zavrsen.
}

I am interested in how I can make it better. I notice it's not nearly as fast as the C++ std::sort.

Here are some measurements I've made:

I've also tried to diagnose the performance problems by measuring how often each algorithm is used for an array of specific sortedness:

But I still can't figure out what's exactly slowing it down to be more than 100 times slower than C++ std::sort is. Can you figure it out? Or can you make my code better in some other way?

Answer 1

The generated assembly code is very inefficient!

First example.

Ley's look at this small part right at the top:

If gornja_granica-donja_granica<2
AsmStart
   ret
AsmEnd
EndIf

This is its assembly code in a readable form:

    finit
    fld dword ptr [gornja_granica]
    fld dword ptr [donja_granica]
    fsubp
    mov dword ptr [result],0x40000000 #IEEE754 hex of 2
    fld dword ptr [result]
    fcomip
    fstp dword ptr [result]
    jna secondOperandOfTheComparisonIsSmallerOrEqualLabel914728
    fld1
    jmp endOfTheLessThanComparisonLabel862181
secondOperandOfTheComparisonIsSmallerOrEqualLabel914728:
    fldz   ; 2 LT (a-b)
endOfTheLessThanComparisonLabel862181:

#Comparing the just-calculated expression with 0...
    fistp dword ptr [result]
    mov eax, dword ptr [result]
    test eax,eax
#Branching based on whether the expression is 0...
    jz ElseLabel529946
    ret
    finit
ElseLabel529946:
EndIfLabel210662:

Basically this code wants to arrive at ElseLabel529946 if gornja_granica-donja_granica<2. For branching the only info that you really need comes from the fcomip instruction. It defines the CF and ZF (and PF) in EFLAGS and you could have jumped immediately

• without loading that 0.0 or 1.0
• without storing into a memory variable
• without testing that memory variable
• without the additional jumping

This is an improved code:

    finit
    fld     dword ptr [gornja_granica]
    fld     dword ptr [donja_granica]
    fsubp
    mov     dword ptr [result], 0x40000000     ; IEEE754 hex of 2
    fld     dword ptr [result]
    fcomip
    fstp    st(0)                              ; Clears FPU stack
    jna     ElseLabel529946
    ret
    finit
ElseLabel529946:

Please notice that to throw away st(0), you don't need to move to memory. Copy st(0) to itself and have the FPU stack popped.

And this improves still further. Less memory access and shorter code!

    finit
    fld     dword ptr [gornja_granica]
    fsub    dword ptr [donja_granica]
    fld1
    fadd    st(0), st(0)                       ; st(0) == 1 + 1
    fcomip
    fstp                                       ; Clears FPU stack
    jna      ElseLabel529946
    ret
ElseLabel529946:

Second example.

While i<7 | i=7

This should be written as While i<=7

I've looked at the assembly code for it and I have seen the same inefficiencies as above. But because of the | operator their negative impact is still worse.

Third example.

sredina_niza:=sredina_niza-mod(sredina_niza,1)

The assembly code for the mod() function uses a lot of instructions. What your AEC needs is an int() function for which you can get by with a mere frndint (Round to integer) instruction.
This:

sredina_niza:=int(sredina_niza)

would then be much faster.

---

Knowing the forementioned, I have no doubt that the MergeSort or QuickSort would be any less inefficient.

Answer 2

A conceptual problem

The idea to choose between MergeSort and QuickSort looks very promising, but because the code that makes the decision is so lengthy and because that code gets repeated on every recursive call, the program is spending 99% of its time deciding and only 1% of its time sorting. That's a bad trade-off!

Also consider:

While i < j
    razvrstanost := razvrstanost + (originalni_niz[i] < originalni_niz[i+1])
    i := i + 1
EndWhile

A cascade of comparing adjacent elements is typical for the lesser sorting methods. Because in your program this cascade is repeated on arrays that get smaller and smaller, you can not hope for this approach to lead to something better/faster than an humble BubbleSort.

My suggestions:

Find out where it leads you if you apply the current decision process only once on the original array.

Simplify the decision process. Go for Less Accurate but Much Faster.

Why c++ std::sort is much faster

Apart from not suffering from the above conceptual problem, that library function

• will have been written directly in Assembly or at least in some higher level language that translates very closely to Assembly.

• will use 32-bit integers as much as possible (array indexing, counting, ...) Your project exclusively works with single precision floating point variables.

• will avoid using FPU instructions whenever possible. e.g. copying variables even if they represent floats:

    mov eax, [donja_granica]
    mov [i], eax
  

  Your code makes a detour via the FPU stack

    #i := donja_granica
    finit
    fld   dword ptr [donja_granica]
    fstp  dword ptr [TEMP]
    mov   edx, dword ptr [TEMP]
    mov   dword ptr [i], edx
  

• will use the normal stack in a straightforward fashion. e.g. preserving the LeftBound

    push  dword ptr [donja_granica]
  

  Your code uses a series of arrays to mimic several stacks:

    #stog_s_donjim_granicama[vrh_stoga] := donja_granica
    finit
    fld   dword ptr [donja_granica]
    fstp  dword ptr [TEMP]
    mov   edx, dword ptr [TEMP]
    fld   dword ptr [vrh_stoga]
    fistp dword ptr [TEMP]
    mov   ebx, dword ptr [TEMP]
    mov   dword ptr [stog_s_donjim_granicama+4*ebx], edx
  

• ...

What you can do

The idea of your sorting methods is to partition the array into ever smaller pieces until such a piece is of length 1 or 2. You correctly return immediately for a length of 1, but for a length of 2 your code executes pointlessly all of those very costly calculations (using pow(), mod(), ln(), exp()) in order to assign values to razvrstanost_na_potenciju[i], polinom_pod_apsolutnom, Eulerov_broj_na_koju_potenciju, koliko_usporedbi_ocekujemo_od_QuickSorta, and koliko_usporedbi_ocekujemo_od_MergeSorta - values that will not be used.
This is the major reason why the code is slow, since reductions downto a length of 2 are very common.

In the line razvrstanost := razvrstanost / ((gornja_granica-donja_granica-1)/2) - 1 you are expecting, that for an already sorted partition the value be 1.
But what if this should ever produce 0.99999999 or 1.00000001 ? Floating point divisions tend to do this.
Then the line If razvrstanost = 1 will be missed and the code will go haywire. Could be the reason why the program crashes.

Next code tries to address both concerns:

razvrstanost := 0
i := donja_granica
j := gornja_granica - 1    ; This optimizes the following WHILE
While i < j
    razvrstanost := razvrstanost + (originalni_niz[i] < originalni_niz[i+1])
    i := i + 1
EndWhile

j := j - donja_granica

If razvrstanost = j
    broj_vec_poredanih_podniza := broj_vec_poredanih_podniza + 1
    ...

ElseIf razvrstanost = 0
    broj_obrnuto_poredanih_podniza := broj_obrnuto_poredanih_podniza + 1
    ...

Else
    i := 2
    razvrstanost := razvrstanost / (j / i) - 1
    While i <= 7 
        razvrstanost_na_potenciju[i] := pow(abs(razvrstanost), i)
        razvrstanost_na_potenciju[i] := ...
        i := i + 1
    EndWhile
    polinom_pod_apsolutnom := ...
    Eulerov_broj_na_koju_potenciju := ...
    koliko_usporedbi_ocekujemo_od_QuickSorta := ...
    koliko_usporedbi_ocekujemo_od_MergeSorta := ...
    If koliko_usporedbi_ocekujemo_od_MergeSorta < koliko_usporedbi_ocekujemo_od_QuickSorta
        broj_pokretanja_MergeSorta := broj_pokretanja_MergeSorta + 1
        ...

    Else ;QuickSort algoritam
        broj_pokretanja_QuickSorta := broj_pokretanja_QuickSorta + 1
        ...

    EndIf
EndIf

---

If (gdje_smo_u_prvom_nizu = sredina_niza | originalni_niz[gdje_smo_u_drugom_nizu] < originalni_niz[gdje_smo_u_prvom_nizu]) & gdje_smo_u_drugom_nizu < gornja_granica

Because your AEC does not perform an early out on the | operator in this complex expression, everything in it is evaluated every single time. Moreover this expression can at some point read past the last element of the array.
Next code, using simple If's, avoids reading array elements unnecessarily or illegally. I believe it's also easier to understand.

i := donja_granica
gdje_smo_u_prvom_nizu := donja_granica
gdje_smo_u_drugom_nizu := sredina_niza
While i < gornja_granica
    If gdje_smo_u_prvom_nizu = sredina_niza
        PickRightSide := 1
    ElseIf gdje_smo_u_drugom_nizu = donja_granica
        PickRightSide := 0
    Else
        PickRightSide := (originalni_niz[gdje_smo_u_drugom_nizu] < originalni_niz[gdje_smo_u_prvom_nizu])
    Endif
    If PickRightSide = 1
        pomocni_niz[i] := originalni_niz[gdje_smo_u_drugom_nizu]
        gdje_smo_u_drugom_nizu := gdje_smo_u_drugom_nizu + 1
    Else
        pomocni_niz[i] := originalni_niz[gdje_smo_u_prvom_nizu]
        gdje_smo_u_prvom_nizu := gdje_smo_u_prvom_nizu + 1
    EndIf
    i := i + 1
EndWhile

---

pomocna_varijabla_za_zamijenu := originalni_niz[i + 1]
originalni_niz[i + 1] := originalni_niz[gornja_granica - 1]
originalni_niz[gornja_granica - 1] := pomocna_varijabla_za_zamijenu
gdje_je_pivot := i + 1

This snippet can be optimized.
If you assign gdje_je_pivot first, you can avoid the index addition [i + 1] twice. And because at this point in the code originalni_niz[gornja_granica - 1] is stored in the pivot variable, you should get it from there which will be a lot faster.

gdje_je_pivot := i + 1
pomocna_varijabla_za_zamijenu := originalni_niz[gdje_je_pivot]
originalni_niz[gdje_je_pivot] := pivot
originalni_niz[gornja_granica - 1] := pomocna_varijabla_za_zamijenu

---

The simplest change you can make to AEC is to dismiss that myriad of finit instructions. When every snippet in the program always pops everything it pushes (and your code seems to work that way), then you only need to use finit once and only once at the start.

You should special-case some very common operations if you desire speed.

• To copy a simple variable to another simple variable, you don't need to use the FPU. e.g. i := donja_granica

    mov     eax, [donja_granica]
    mov     [i], eax
  

• Incrementing a simple variable. e.g. inc i

    fld1
    fadd    dword ptr [i]
    fstp    dword ptr [i]
  

• Decrementing a simple variable. e.g. dec i

    fld1
    fsubr   dword ptr [i]
    fstp    dword ptr [i]
  

• If you would compile a short list of frequently used immediates (iList dw 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10), then using these would be a breeze. Assigning would be very efficient. e.g. i := 2

    fild    word ptr [iList + 4]
    fstp    dword ptr [i]
  

There's nothing that prevents you from using the normal stack instead of dedicated arrays

#AsmStart
push  dword ptr [donja_granica]
#AsmEnd

The segmentation fault

I see 3 reasons why this could happen:

• Reading past the last element of the array. See above.
• The code goes haywire if the execution misses If razvrstanost=1. See above.
• The dedicated arrays that mimic a stack are too small. This can happen when the pivotting mechanism, continually partitions the array in a very big and a very small chunk. On an array with 65536 elements, the recursion depth will rapidly exceed 1024 (dimension of your special arrays).