1 /*
   2  * Ovo je prijepis mog hibridnog algoritma razvrstavanja da se može
   3  * pokrenuti na JavaScriptinoj virtualnoj mašini. Kako bi se AEC-om mogla
   4  * ciljati JavaScriptina virtualna mašina, napravio sam novi compiler.
   5  * Ovaj puta je pisan u C++-u, radio sam i novi parser i novi tokenizer.
   6  * Također sam malo promijenio sintaksu, da omogućim pisanje čistijeg koda
   7  * te da podržavam različite vrste podataka (prije je AEC podržavao samo
   8  * 32-bitne decimalne brojeve). Novi compiler proizvodi WebAssembly,
   9  * standardizirani oblik JavaScriptinog bytecodea. Izvorno je WebAssembly
  10  * bio Mozillin standard, ali danas ga podržavaju gotovo sve JavaScriptine
  11  * virtualne mašine. Ovdje ciljamo primarno na NodeJS, JavaScriptinu
  12  * virtualnu mašinu koju razvija Google i primarno je namijenjena da se
  13  * vrti na serverima (no može se pokrenuti i na veoma slabim računalima).
  14  */
  15 
  16 // Uvezimo prvo neke funkcije iz JavaScripta, koje će nam trebati...
  17 Function daj_velicinu_niza() Which Returns Integer32 Is External;
  18 Function kopiraj_niz_na_adresu(
  19     Integer32Pointer adresa) Which Returns Nothing Is External;
  20 Function printString(CharacterPointer str) Which Returns Nothing Is External;
  21 Function printInteger(Integer32 n) Which Returns Nothing Is External;
  22 Function printFloat(Decimal32 x) Which Returns Nothing Is External;
  23 Function pocni_mjerenje_vremena() Which Returns Nothing Is External;
  24 Function zavrsi_mjerenje_vremena() Which Returns Nothing Is External;
  25 Function izvijesti_o_obrnuto_poredanim_nizovima(
  26     Integer32 n) Which Returns Nothing Is External;
  27 Function
  28 izvijesti_o_poredanim_nizovima(Integer32 n) Which Returns Nothing Is External;
  29 Function izvijesti_o_pokretanju_QuickSorta(
  30     Integer32 n) Which Returns Nothing Is External;
  31 Function izvijesti_o_pokretanju_MergeSorta(
  32     Integer32 n) Which Returns Nothing Is External;
  33 Function izvijesti_o_pokretanju_SelectSorta(
  34     Integer32 n) Which Returns Nothing Is External;
  35 Function
  36 izvijesti_JavaScript_o_nedostatku_memorije() Which Returns Nothing Is External;
  37 
  38 Integer32 DEBUG : = 0, broj_mjerenja : = 0; // broj_mjerenja bit će koristan za
  39                                             // pokretanje raznih algoritama
  40                                             // ovisno o rednom broju mjerenja,
  41                                             //što dobro dođe za
  42                                             // eksperimentiranje s algoritmima.
  43 
  44 // Napravimo sada omotnicu oko WebAssemblerske naredbe "memory.grow"...
  45 Function zauzmi_memorijske_stranice(Integer32 broj_stranica) Which Returns
  46     CharacterPointer
  47     Does { // Vitičasta zagrada ovdje je opcionalna, compiler ju ignorira. No,
  48            // dobro dođe kada pišemo AEC-ovski program u nekom IDE-u koji je
  49            // primarno namijenjen za C-olike jezike, tada on može razumijeti da
  50            // je ono između vitičastih zagrada blok naredbi.
  51   Integer32 nova_adresa_u_stranicama
  52       : = asm_i32 //"asm_i32" kaže compileru da umetne asemblerski kod, i da
  53                   // pretpostavi da će se nakon njega na sistemskom stogu
  54                   // nalaziti vrijednost tipa "i32". To očito nije točno ako
  55                   // netko prebaci JavaScript virtualnu mašinu u 64-bitni
  56                   // način rada, ali nadam se da to nitko neće napraviti.
  57                   // Vjerojatnost da će JavaScript virtualnoj mašini trebati
  58                   // više nego 4GB RAM-a je zanemariva, a vjerojatnost da će
  59                   // se neki korisni programi srušiti zbog prebacivanja u
  60                   // 64-bitni način rada nije baš zanemariva.
  61         ("(memory.grow\n"
  62          "\t(local.get 0)\n" // Prvi (nulti) argument funkcije,
  63                              //"broj_stranica".
  64          ")\n");
  65   If nova_adresa_u_stranicama = -1 Then { // Ako nema više
  66                                           // slobodne memorije...
  67     Return(-1); // Ne stavim li zagrade oko "-1", ClangFormat će misliti da je
  68                 // "Return" ime neke varijable.
  69   }
  70   EndIf; // Ni točka-zarez ovdje nije potreban, ali pomaže IDE-ovima da razumiju
  71          // programski kôd.
  72   Return nova_adresa_u_stranicama * 64 * 1024; // Na JavaScript Virtualnoj
  73                                                // Mašini, jedna stranica
  74                                                //(page) iznosi 64 KB.
  75 }
  76 EndFunction;
  77 
  78 Integer32 velicina_niza;
  79 Integer32Pointer originalni_niz, pomocni_niz; // To su globalne varijable,
  80                                               // po defaultu su u nuli,
  81                                               // dakle "originalni_niz" i
  82                                               //"pomocni_niz" su na početku
  83                                               // programa nulti pokazivači.
  84 
  85 Integer32 broj_obrnuto_poredanih_podniza, broj_vec_poredanih_podniza,
  86     broj_pokretanja_QuickSorta, broj_pokretanja_MergeSorta,
  87     broj_pokretanja_SelectSorta;
  88 
  89 // Sad ćemo implementirati neke matematičke funkcije koje će nam trebati.
  90 // Ne možemo pozvati JavaScriptine matematičke funkcije, jer one su metode
  91 // singletona "Math", a ne postoji standardizirani način da se zovu
  92 // metode JavaScriptinih objekata iz WebAssemblyja.
  93 Decimal32 PRECISION : = 128; // Ovdje možemo balansirati između brzine i
  94                              // preciznosti. Ako smo previše precizni, bit
  95                              //ćemo spori. Ako smo previše neprecizni, lako
  96                              // se može dogoditi da precijenimo koliko se
  97                              // duboko rekurzija smije granati i izazovemo
  98                              // stack overflow.
  99 
 100 Decimal32
 101     memoizacija_prirodnog_logaritma[8192]; // Memoizacija je dio memorije u koju
 102                                            // se spremaju već izračunati podaci,
 103                                            // da se ne računaju više puta.
 104 
 105 Function Eulerov_broj_na_potenciju(Decimal32 x)
 106     Which Returns Decimal32 Is Declared; // Vidi dolje za pojašnjenje ovoga.
 107 
 108 Function prirodni_logaritam(Decimal32 x) Which Returns Decimal32 Does {
 109   If x < 1 Then { Return(-prirodni_logaritam(1 / x)); }
 110   EndIf;
 111   If(x < 8192 and
 112      not(memoizacija_prirodnog_logaritma[asm_f32( // Vidi iduću funkciju za
 113                                                   // pojašnjenje ovoga...
 114              "(f32.nearest (local.get 0))")] = 0)) Then {
 115     Return
 116         memoizacija_prirodnog_logaritma[asm_f32("(f32.nearest (local.get 0))")];
 117   }
 118   EndIf;
 119   If x > 8192 Then {
 120     Return 1 + prirodni_logaritam(x / Eulerov_broj_na_potenciju(1));
 121   }
 122   EndIf;
 123   // Prirodni logaritam je integral od 1/x u intervalu od 1 do x,
 124   // srednjoškolska matematika.
 125   Decimal32 zbroj : = 0, epsilon : = (x - 1) / (5 * PRECISION), i : = 1;
 126   While(epsilon > 0 and i < x) or (epsilon < 0 and i > x) Loop {
 127     zbroj += epsilon / i;
 128     i += epsilon; // Preuzeo sam naredbe "+=", "-=", "*=" i "/=" iz C-olikih
 129                   // jezika, smatram da znatno skraćuju neke kodove, a da ih ne
 130                   // čine nečitkima.
 131   }
 132   EndWhile;
 133   If x < 8192 Then {
 134     Return
 135         memoizacija_prirodnog_logaritma[asm_f32("(f32.nearest (local.get 0))")]
 136         : = zbroj;
 137   }
 138   EndIf;
 139   Return zbroj;
 140 }
 141 EndFunction;
 142 
 143 Decimal32
 144     memoizacija_Eulerovog_algoritma[512]; // Možda malo ubrza program, gotovo
 145                                           // sigurno ga neće usporiti...
 146 
 147 Function abs(Decimal32 x) Which Returns Decimal32 Is
 148     Declared; // Deklarirat ćemo funkciju "abs" da se može koristiti prije no
 149               // što se definira.
 150 
 151 Function Eulerov_broj_na_potenciju(Decimal32 x) Which Returns Decimal32 Does {
 152   If(abs(x) < 64 and
 153      not(memoizacija_Eulerovog_algoritma
 154              [asm_f32("(f32.nearest (f32.mul (f32.const 4) (local.get 0)))") +
 155               256] = 0))
 156       Then { // Koristio sam ovdje umetnuti asembler zato što ništa drugo što
 157              // napišem u AEC-u neće učiniti da compiler koji sam napravio
 158              // pozove asemblersku instrukciju "f32.nearest" (poznatu kao
 159              // "round" u drugim programskim jezicima), a mnogo je lakše
 160              // napisati malo umetnutog asemblera nego mijenjati i recompilirati
 161              // compiler.
 162     Return memoizacija_Eulerovog_algoritma
 163         [asm_f32("(f32.nearest (f32.mul (f32.const 4) (local.get 0)))") + 256];
 164   }
 165   EndIf;
 166   // Eulerov Algoritam iz Matematike 2...
 167   Decimal32 i : = 0, y : = 1, epsilon : = x / PRECISION;
 168   While(epsilon > 0 and i < x) or (epsilon < 0 and i > x) Loop {
 169     y += epsilon * y;
 170     i += epsilon;
 171   }
 172   EndWhile;
 173   If abs(x) < 64 Then {
 174     Return memoizacija_Eulerovog_algoritma
 175         [asm_f32("(f32.nearest (f32.mul (f32.const 4) (local.get 0)))") + 256]
 176         : = y;
 177   }
 178   EndIf;
 179   Return y;
 180 }
 181 EndFunction;
 182 
 183 Function abs(Decimal32 x) Which Returns Decimal32 Does {
 184   // U svoj sam programski jezik ugradio uvijetni "?:" operator kakav
 185   // postoji u C-u, C++-u i JavaScriptu. Izgleda malo ružno, ali nekad zna
 186   // znatno skratiti programske kodove. Odlučio sam implementirati desno
 187   // asocijativan uvijetni operator, kakav je u C-u, C++-u i JavaScriptu,
 188   // a ne lijevo asocijativan kakav je u PHP-u i srodnim jezicima.
 189   // Jednostavno mi ima više smisla da uvijetni operator bude asocijativan
 190   // na desno nego na lijevo.
 191   Return(x < 0) ?    // Ako je x manji od 0...
 192       -x             //...vrati (proglasi rezultatom) -x...
 193                 : x; // inače, proglasi x rezultatom.
 194 }
 195 EndFunction;
 196 
 197 Function ostatak_pri_dijeljenju(Decimal32 x,
 198                                 Decimal32 y) Which Returns Decimal32 Does {
 199   If DEBUG = 1 Then {
 200     printString("Zatrazen je ostatak pri dijeljenju od brojeva: ");
 201     // Neću upotrebljavati hrvatske znakove u stringovima, jer ću
 202     // naletjeti na probleme pri pretvorbi u JavaScriptin string.
 203     printFloat(x);
 204     printFloat(y);
 205     printString("Sada ce se program mozda srusiti...");
 206   }
 207   EndIf;
 208   If abs(x / y) > Eulerov_broj_na_potenciju(prirodni_logaritam(2) * 63) Then {
 209     Return 0; // Imate bolju ideju što da se radi u slučaju da količnik
 210               // ne stane niti u Integer64 (C-ovski "long long")?
 211   }
 212   EndIf;
 213   Return x - y *Integer64(x / y); // Ako napišem "Integer32",
 214                                   // riskiram da će JavaScript
 215                                   // virtualna mašina prekinuti
 216                                   // izvođenje programa jer je
 217                                   // broj "x/y" izvan intervala
 218                                   // koji 32-bitni cijeli brojevi
 219                                   // mogu prikazati (od oko dvije
 220                                   // milijarde u pozitivno i
 221                                   // negativno).
 222 }
 223 EndFunction;
 224 
 225 Function pow(Decimal32 x, Decimal32 y) Which Returns Decimal32 Does {
 226   Decimal32 result
 227       : = Eulerov_broj_na_potenciju(prirodni_logaritam(abs(x)) * y);
 228   Return x =
 229       0 ? 0 : ostatak_pri_dijeljenju(x, 2) = 1 and x < 0 ? -result : result;
 230 }
 231 EndFunction;
 232 
 233 // I sada krećemo pisati taj hibridni algoritam razvrstavanja...
 234 Function hybrid_sort(Integer32 donja_granica, Integer32 gornja_granica,
 235                      Integer32 dubina_rekurzije) Which Returns Nothing Does {
 236   If gornja_granica - donja_granica < 2 Then { // Ako je niz duljine manje od
 237                                                // 2 (0 ili 1), znači da je već
 238                                                // poredan, pa prekidamo
 239                                                // izvođenje ovog potprograma.
 240     Return;
 241   }
 242   ElseIf gornja_granica - donja_granica = 2 Then { // Najčesći slučaj,
 243                                                    // vrijedi ga posebno
 244                                                    // obraditi jer time
 245                                                    // možemo znatno ubrzati
 246                                                    // program.
 247     If ValueAt(originalni_niz + donja_granica) >
 248         ValueAt(originalni_niz + donja_granica + 1) Then {
 249       Integer32 pomocna_varijabla_za_zamijenu
 250           : = ValueAt(originalni_niz + donja_granica);
 251       ValueAt(originalni_niz + donja_granica)
 252           : = ValueAt(originalni_niz + donja_granica + 1);
 253       ValueAt(originalni_niz + donja_granica + 1)
 254           : = pomocna_varijabla_za_zamijenu;
 255     }
 256     EndIf;
 257     Return;
 258   }
 259   ElseIf gornja_granica -
 260       donja_granica<8 or asm_i32("(global.get $stack_pointer)")> 4 * 1024 -
 261       73 Then {
 262   // Za male je nizove SelectionSort brži i od MergeSorta i QuickSorta. Također,
 263   // kako nije rekurzivan, može se koristiti i kad posve potrošimo memoriju na
 264   // sistemskom stogu(na JavaScript Virtualnoj Mašini to jest ne više nego 4 KB,
 265   // kako bijaše u doba Netscapea 2, godine 1996, tako i danas).
 266   broj_pokretanja_SelectSorta:
 267     = broj_pokretanja_SelectSorta + 1;
 268     Integer32 i : = donja_granica;
 269     While i < gornja_granica Loop {
 270       Integer32 gdje_je_minimum : = i;
 271       Integer32 j : = i + 1;
 272       While j < gornja_granica Loop {
 273         If ValueAt(originalni_niz + gdje_je_minimum) >
 274             ValueAt(originalni_niz + j) Then {
 275         gdje_je_minimum
 276             /*
 277              * ClangFormat (koji koristim za formatiranje AEC programa, a
 278              * primarno je namijenjen za C-olike jezike) pogrešno tumači
 279              * AEC-ov operator pridruživanja ":=" kao C-ovu oznaku za labele
 280              * ':' plus C-ov operator pridruživanja '='. Ne vidim nekakvo
 281              * jednostavno rješenje tog problema. Na sreću, AEC-ov tokenizer,
 282              * još od najranije verzije, trpi ako se stavi whitespace znak
 283              * (razmak, tabulator ili znak za novi red) između ':' i '=' u
 284              * operatoru ":=", ali svejedno to ne izgleda dobro.
 285              */
 286             :
 287           = j;
 288         }
 289         EndIf;
 290         j += 1;
 291       }
 292       EndWhile;
 293       Integer32 pomocna_varijabla_za_zamijenu : = ValueAt(originalni_niz + i);
 294       ValueAt(originalni_niz + i) : = ValueAt(originalni_niz + gdje_je_minimum);
 295       ValueAt(originalni_niz + gdje_je_minimum)
 296           : = pomocna_varijabla_za_zamijenu;
 297       i += 1;
 298     }
 299     EndWhile;
 300     Return;
 301   }
 302   EndIf;
 303   Decimal32 razvrstanost : = 0;
 304   Integer32 i : = donja_granica, je_li_niz_vec_poredan : = 1;
 305   While i < gornja_granica - 1 Loop {
 306     razvrstanost +=
 307         (ValueAt(originalni_niz + i) < ValueAt(originalni_niz + i + 1) or
 308              ValueAt(originalni_niz + i) = ValueAt(originalni_niz + i + 1));
 309     If ValueAt(originalni_niz + i) > ValueAt(originalni_niz + i + 1) Then {
 310     je_li_niz_vec_poredan:
 311       = 0;
 312     }
 313     EndIf;
 314     i += 1;
 315   }
 316   EndWhile;
 317 razvrstanost:
 318   = razvrstanost / ((gornja_granica - donja_granica - 1) / 2.) - 1;
 319   // Provjeri je li sve u redu, i, ako nije, obavijesti.
 320   If abs(razvrstanost) > 1 Then {
 321     // To ne smije biti...
 322     printString("Apsolutna vrijednost razvrstanosti je veca od 1!");
 323     printString("Relevantni dio niza iznosi:"); // Da se ne moram baktati s
 324                                                 // debuggerima za JavaScript
 325                                                 // virtualnu mašinu ako dođe
 326                                                 // do problema, lakše mi
 327                                                 // je ispisati brojeve u
 328                                                 // programu nego tražiti
 329                                                 // kako narediti
 330                                                 // debuggeru da ih
 331                                                 // ispiše.
 332   i:
 333     = donja_granica;
 334     While i < gornja_granica Loop {
 335       printInteger(ValueAt(originalni_niz + i));
 336       i += 1;
 337     }
 338     EndWhile;
 339     printString("Kraj relevantnog dijela niza!");
 340   }
 341   EndIf;
 342   If je_li_niz_vec_poredan and not(razvrstanost = 1 or razvrstanost > 1) Then {
 343     // Opet ne smije biti...
 344     printString("Niz je poredan, a razvrstanost nije 1.");
 345     printString("Relevantni dio niza iznosi:");
 346   i:
 347     = donja_granica;
 348     While i < gornja_granica Loop {
 349       printInteger(ValueAt(originalni_niz + i));
 350       i += 1;
 351     }
 352     EndWhile;
 353     printString("Kraj relevantnog dijela niza!");
 354   }
 355   EndIf;
 356   If not(je_li_niz_vec_poredan) and (razvrstanost = 1 or razvrstanost > 1)
 357                                         Then {
 358     // Open ne smije biti...
 359     printString("Razvrstanost je 1, a niz nije poredan!");
 360     printString("Relevantni dio niza iznosi:");
 361   i:
 362     = donja_granica;
 363     While i < gornja_granica Loop {
 364       printInteger(ValueAt(originalni_niz + i));
 365       i += 1;
 366     }
 367     EndWhile;
 368     printString("Kraj relevantnog dijela niza!");
 369   }
 370   EndIf;
 371   // Idemo dalje...
 372   Decimal32 razvrstanost_na_potenciju[8] : = {1}; // Formula će se brže
 373                                                   // izračunati ako ne
 374                                                   // pozivamo "pow" gdje
 375                                                   // ne treba (kad je
 376                                                   // eksponent prirodan
 377                                                   // broj).
 378 i:
 379   = 1;
 380   While i < 8 Loop {
 381     razvrstanost_na_potenciju[i]
 382         : = razvrstanost_na_potenciju[i - 1] * razvrstanost;
 383     i += 1;
 384   }
 385   EndWhile;
 386   // Formula koju je ispisao genetski algoritam za predviđanje koliko će
 387   // usporedbi QuickSort napraviti:
 388   // https://github.com/FlatAssembler/ArithmeticExpressionCompiler/tree/master/QuickSort/Genetic_algorithm_for_deriving_the_formula
 389   Decimal32 polinom_pod_apsolutnom
 390       : = 2.38854 * razvrstanost_na_potenciju[7] -
 391           0.284258 * razvrstanost_na_potenciju[6] -
 392           1.87104 * razvrstanost_na_potenciju[5] +
 393           0.372637 * razvrstanost_na_potenciju[4] +
 394           0.167242 * razvrstanost_na_potenciju[3] -
 395           0.0884977 * razvrstanost_na_potenciju[2] + 0.315119 * razvrstanost;
 396   Decimal32 Eulerov_broj_na_koju_potenciju
 397       : = (prirodni_logaritam(gornja_granica - donja_granica) +
 398            prirodni_logaritam(
 399                prirodni_logaritam(gornja_granica - donja_granica))) *
 400               1.05 +
 401           (prirodni_logaritam(gornja_granica - donja_granica) -
 402            prirodni_logaritam(
 403                prirodni_logaritam(gornja_granica - donja_granica)) -
 404            prirodni_logaritam(2)) *
 405               0.9163 * abs(polinom_pod_apsolutnom);
 406   Decimal32 koliko_usporedbi_ocekujemo_od_QuickSorta
 407       : = Eulerov_broj_na_potenciju(Eulerov_broj_na_koju_potenciju);
 408   Decimal32 koliko_usporedbi_ocekujemo_od_MergeSorta
 409       : = (mod(broj_mjerenja, 2) + 1) *
 410           (gornja_granica -
 411            donja_granica) * // Nisam siguran treba li ovdje
 412                             // pisati "2 * (gornja_granica...".
 413                             // S jedne strane, MergeSort radi
 414                             // dvije petlje, jedna za spajanje
 415                             // dijelova originalnog niza u
 416                             // pomoćni niz, a druga za kopiranje
 417                             // pomoćnog niza u originalni. S
 418                             // druge strane, iz mjerenja se čini
 419                             // da je cjelokupni algoritam brži
 420                             // ako se ne množi s 2. Zato ćemo
 421                             // nekada množiti s dva, a nekada ne,
 422                             // pa ćemo preciznijim mjerenjima
 423                             // vidjeti što je bolje.
 424           prirodni_logaritam(gornja_granica - donja_granica) /
 425           prirodni_logaritam(2);
 426   // I sada kreće grananje na temelju izračunatog...
 427   If razvrstanost = 1 or razvrstanost > 1 Then {
 428     broj_vec_poredanih_podniza += 1;
 429     Return;
 430   }
 431   ElseIf razvrstanost = -1 or razvrstanost < -1 Then {
 432     broj_obrnuto_poredanih_podniza += 1;
 433     Integer32 i : = donja_granica;
 434     Integer32 j : = gornja_granica - 1;
 435     While i < gornja_granica Loop {
 436       ValueAt(pomocni_niz + i) : = ValueAt(originalni_niz + j);
 437       j -= 1;
 438       i += 1;
 439     }
 440     EndWhile;
 441   i:
 442     = donja_granica;
 443     While i < gornja_granica Loop {
 444       ValueAt(originalni_niz + i) : = ValueAt(pomocni_niz + i);
 445       i += 1;
 446     }
 447     EndWhile;
 448     Return;
 449   }
 450   ElseIf(koliko_usporedbi_ocekujemo_od_MergeSorta <
 451              koliko_usporedbi_ocekujemo_od_QuickSorta or
 452          dubina_rekurzije > pow(2, 18 - prirodni_logaritam(velicina_niza) /
 453                                             prirodni_logaritam(2))
 454          // JavaScriptina virtualna mašina ima
 455          // 4KB memorije na sistemskom stogu,
 456          // i alociranje više heap memorije
 457          // ne mijenja tu nesretnu činjenicu.
 458          // Ne znam kako Emscripten (modificirana
 459          // verzija CLANG-a koja compilira
 460          // C++ u WebAssembly) to rješava.
 461          ) and
 462       not(gornja_granica - donja_granica =
 463               velicina_niza and not(mod(broj_mjerenja, 3)))
 464       // Izgleda da je, iz nekog razloga, program brži ako se QuickSort
 465       // pokrene barem jednom, no probajmo raditi preciznija mjerenja.
 466       Then {
 467     // MergeSort algoritam (približno poredani podnizovi,
 468     // za koje je MergeSort efikasniji od QuickSorta,
 469     // a moj ga program također koristi kada ima još
 470     // malo mjesta na sistemskom stogu, pa QuickSort
 471     // nije opcija)...
 472     broj_pokretanja_MergeSorta += 1;
 473     Integer32 sredina_niza : = (gornja_granica + donja_granica) / 2;
 474     // Prvo, rastavi niz na koji pokazuje pokazivač "originalni_niz"
 475     // na niz od originalni_niz+donja_granica do
 476     // originalni_niz+sredina_niza i niz od
 477     // originalni_niz+sredina_niza do
 478     // originalni_niz+gornja_granica,
 479     // i poredaj ta dva niza.
 480     hybrid_sort(donja_granica, sredina_niza, dubina_rekurzije + 1);
 481     hybrid_sort(sredina_niza, gornja_granica, dubina_rekurzije + 1);
 482     // Spajanje nizova originalni_niz[donja_granica..sredina_niza]
 483     // i originalni_niz[sredina_niza..gornja_granica] u jedan niz...
 484     Integer32 i : = donja_granica;
 485     Integer32 gdje_smo_u_prvom_nizu : = donja_granica;
 486     Integer32 gdje_smo_u_drugom_nizu : = sredina_niza;
 487     While i < gornja_granica Loop {
 488       If(gdje_smo_u_prvom_nizu =
 489              sredina_niza or
 490              ValueAt(originalni_niz + gdje_smo_u_drugom_nizu) <
 491                  ValueAt(originalni_niz + gdje_smo_u_prvom_nizu)) and
 492           gdje_smo_u_drugom_nizu < gornja_granica Then {
 493         ValueAt(pomocni_niz + i)
 494             : = ValueAt(originalni_niz + gdje_smo_u_drugom_nizu);
 495         gdje_smo_u_drugom_nizu += 1;
 496       }
 497       Else {
 498         ValueAt(pomocni_niz + i)
 499             : = ValueAt(originalni_niz + gdje_smo_u_prvom_nizu);
 500         gdje_smo_u_prvom_nizu += 1;
 501       }
 502       EndIf;
 503       i += 1;
 504     }
 505     EndWhile;
 506   i:
 507     = donja_granica;
 508     While i < gornja_granica Loop {
 509       ValueAt(originalni_niz + i) : = ValueAt(pomocni_niz + i);
 510       i += 1;
 511     }
 512     EndWhile;
 513     Return;
 514   }
 515   Else { // QuickSort algoritam (nasumično ispremještani podnizovi)...
 516     broj_pokretanja_QuickSorta += 1;
 517     // Daljnji kod je približno prepisan s
 518     // https://www.geeksforgeeks.org/quick-sort/
 519     // Iskreno, ne razumijem ni ja točno kako funkcionira.
 520     // On navodno preuređuje niz tako da svi elementi koji su manji
 521     // od onog koji je bio prvi (pivot) dođu prije njega, a ostali
 522     // poslije njega.
 523     Integer32 pivot : = ValueAt(originalni_niz + gornja_granica - 1);
 524     Integer32 i : = donja_granica - 1;
 525     Integer32 j : = donja_granica;
 526     Integer32 pomocna_varijabla_za_zamijenu;
 527     While j < gornja_granica - 1 Loop {
 528       If ValueAt(originalni_niz + j) < pivot Then {
 529         i += 1;
 530       pomocna_varijabla_za_zamijenu:
 531         = ValueAt(originalni_niz + i);
 532         ValueAt(originalni_niz + i) : = ValueAt(originalni_niz + j);
 533         ValueAt(originalni_niz + j) : = pomocna_varijabla_za_zamijenu;
 534       }
 535       EndIf;
 536       j += 1;
 537     }
 538     EndWhile;
 539   pomocna_varijabla_za_zamijenu:
 540     = ValueAt(originalni_niz + i + 1);
 541     ValueAt(originalni_niz + i + 1)
 542         : = ValueAt(originalni_niz + gornja_granica - 1);
 543     ValueAt(originalni_niz + gornja_granica - 1)
 544         : = pomocna_varijabla_za_zamijenu;
 545     Integer32 gdje_je_pivot : = i + 1;
 546     hybrid_sort(donja_granica, gdje_je_pivot, dubina_rekurzije + 1);
 547     hybrid_sort(gdje_je_pivot, gornja_granica, dubina_rekurzije + 1);
 548     Return;
 549   }
 550   EndIf;
 551   // Ovdje tok programa ne smije doći.
 552   printString("Izgleda da compiler nije ispravno "
 553               "preveo kontrolne strukture!");
 554 }
 555 EndFunction;
 556 
 557 // Ovo je funkcija koju će pozvati JavaScript...
 558 Function pocetna_AEC_funkcija() Which Returns Nothing Does {
 559   If originalni_niz = -1 or pomocni_niz = -1 Then {
 560     Return; // Ako JavaScript nastavlja pokretati ovaj program
 561             // unatoč nedostatku memorije, neka onda on ne radi ništa.
 562   }
 563   EndIf;
 564   // Testiraj matematičke funkcije...
 565   If abs(pow(3, 3) - 27) > 2 Then { // Da, one su jako neprecizne, ali zato
 566                                     // jako brze.
 567     printString("Izgleda da matematicke funkcije ne funkcioniraju dobro.");
 568     printString("pow(3, 3) =");
 569     printFloat(pow(3, 3));
 570   }
 571   EndIf;
 572   // Doznaj veličinu niza iz JavaScripta...
 573   Integer32 prijasnja_velicina_niza : = velicina_niza;
 574 velicina_niza:
 575   = daj_velicinu_niza();
 576   // Ako je potrebno, zauzmi još memorije...
 577   If velicina_niza / (64 * 1024 / 4) +
 578               not(not(mod(velicina_niza, 64 * 1024 / 4))) >
 579           prijasnja_velicina_niza / (64 * 1024 / 4) +
 580               not(not(mod(prijasnja_velicina_niza, 64 * 1024 / 4))) or
 581       prijasnja_velicina_niza = 0 Then {
 582   originalni_niz:
 583     = zauzmi_memorijske_stranice(4 * velicina_niza / (64 * 1024) +
 584                                  not(not(mod(velicina_niza, 64 * 1024 / 4))));
 585   pomocni_niz:
 586     = zauzmi_memorijske_stranice(4 * velicina_niza / (64 * 1024) +
 587                                  not(not(mod(velicina_niza, 64 * 1024 / 4))));
 588     If originalni_niz = -1 or pomocni_niz = -1 Then {
 589       printString("Nema dovoljno memorije za nastavak programa!?");
 590       izvijesti_JavaScript_o_nedostatku_memorije();
 591       Return; // Prekini izvršavanje ovog programa.
 592     }
 593     EndIf;
 594   }
 595   EndIf;
 596   // Sada zatraži od JavaScripta da kopira niz koji treba poredati
 597   // na memorijski prostor koji si (prethodno ili sada) zauzeo.
 598   kopiraj_niz_na_adresu(originalni_niz);
 599 // I sada ga kreni razvrstavati i mjeriti koliko ti treba vremena.
 600 broj_obrnuto_poredanih_podniza:
 601   = broj_vec_poredanih_podniza : = broj_pokretanja_QuickSorta
 602       : = broj_pokretanja_MergeSorta : = broj_pokretanja_SelectSorta
 603       : = 0; // Nisam mogao odoljeti da u svoj programski jezik ne dodam
 604              // ulančano pridruživanje iz C-a, C++-a i JavaScripta (da možemo
 605              // više varijabli postaviti na neku vrijednost u jednoj naredbi).
 606   broj_mjerenja += 1;
 607   pocni_mjerenje_vremena();
 608   hybrid_sort(0, velicina_niza, 0);
 609   zavrsi_mjerenje_vremena();
 610   // Kad završi mjerenje vremena (koje se vrtilo u JavaScriptu),
 611   // obavijesti JavaScript o onome što si ti izmjerio.
 612   izvijesti_o_obrnuto_poredanim_nizovima(broj_obrnuto_poredanih_podniza);
 613   izvijesti_o_poredanim_nizovima(broj_vec_poredanih_podniza);
 614   izvijesti_o_pokretanju_QuickSorta(broj_pokretanja_QuickSorta);
 615   izvijesti_o_pokretanju_MergeSorta(broj_pokretanja_MergeSorta);
 616   izvijesti_o_pokretanju_SelectSorta(broj_pokretanja_SelectSorta);
 617   // Napravi neki osnovni sanity-check, je li niz uistinu poredan?
 618   Integer32 i : = 0;
 619   While i < velicina_niza - 1 Loop {
 620     If ValueAt(originalni_niz + i) > ValueAt(originalni_niz + i + 1) Then {
 621       printString("Niz nije poredan!");
 622       Return; // Nemoj to ispisati više puta, nego prekini program čim
 623               // si uočio prvu nepodudarnost.
 624     }
 625     EndIf;
 626     i += 1;
 627   }
 628   EndWhile;
 629 }
 630 EndFunction;
 631