O(n log n) = n * (ln(n) / ln(2) - 1) + 1

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_sorts
https://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost#P%C5%99%C3%ADklad_v%C3%BDpo%C4%8Detn%C3%AD_n%C3%A1ro%C4%8Dnosti
https://en.wikipedia.org/wiki/Comparison_sort

+---------------------------------------+
| 2 XsortListMerge_m2x_v1_Top_Bounds    |
+---------------------------------------+

3 1 2 2 0 3 1 0                          // input (array_1)

(1) 3 = | 1   =   | 0  =  | 1 = | 0 =    // zjistim skupiny serazenych prvku
        | 2  ===  | 3 === |     |
        | 2 ===== |       |     |


(2) 1    =    0   =   0 =                // spojim po dve skupiny do jedne, opakuji pro ostatni dvojice skupin
    2   ===   1  ===                     // spojovani: porovnavam vrchni prvek skupiny 1 s vrchnim skupiny 2, mensi ulozim do noveho pole
    2  =====  3 =====                    // pozn: vyhodnejsi u spojovani je, kdyz maji obe skupiny podobny pocet prvku
    3 =======

(3) 
         =       =  
        ===   
       =====  
      ======= 
     =========
    ===========
   =============

(4) spojim posledni dve skupiny a hotovo



+---------------------------------------+
| 4 sortListMerge_m2_v2_Top             |
| 7 sortListMerge_m1x_v5_Top_Stack      |  
+---------------------------------------+

(1) = = = = = = = =		// serazene skupiny maji vzdy delku 1

(2) =   =   =   =               // spojim dve skupiny po jedne, opakuji
   === === === ===              // spojovani: porovnavam vrchni prvek skupiny 1 s vrchnim skupiny 2, mensi ulozim do noveho pole

(3)   =       =  
     ===     ===  
    =====   ===== 
   ======= =======

(4) spojim posledni dve skupiny a hotovo


3 1 2 2 0 3 1 0          // input (array_1)

3-1   2-2   0-3   1-0    // compare top of sorted list A (list array-size = 1) with top of sorted list B (list length 1), C-D, E-F, G-H
1 3   2 2   0 3   0 1    // saved output at end in array_2, cmp = 4 (you still copy from array 1 to array 2 and back, need two array or two array with indexes)

1 3 | 2 2 | 0 3 | 0 1    // input (array_2; A-B, C-D, E-F, G-H is now new sorted array with array-size = 2)
1-----2                  // compare first from AB with first from CD, smaller save
1                        // save
  3---2                  // compare next from AB with first from CD, smaller save
      2                  // save
  3-----2                // compare from last AB with last from CD, smaller save
        2                // save
  3                      // save (copy)
1 2 2 3                  // saved output at end (in array_1), cmp + 3

            0-----0      // compare first (EF) with first (GH)
            0            // save
              3---0      // compare next (EF) with first (GH)
                  0      // save
              3-----1    // compare last (EF) with last (GH)
                    1    // save
              3          // save (copy)
            0 0 1 3      // saved output at end (in array_1), cmp + 3

1 2 2 3 | 0 0 1 3        // new sorted lists
1---------0              // compare first (ABCD) with first (EFGH)
          0              // save
1-----------0            // compare first (ABCD) with second (EFGH)
            0            // save
1-------------1          // compare first (ABCD) with third (EFGH)
1                        // save
  2------------1         // compare second (ABCD) with third (EFGH)
               1         // save
  2--------------3       // compare second (ABCD) with last (EFGH)
  2                      // save
    2------------3       // compare third (ABCD) with last (EFGH)
    2                    // save
      3----------3       // compare last (ABCD) with last (EFGH)
      3                  // save
                 3       // save (copy), cmp + 7
==================
0 0 1 1 2 2 3 3          // output in array_2, return handle to array, suma(cmp) = 4+3+3+7 = 17



+---------------------------------------+
| 5 Xhybrid_Sort4_ListMerge_m2_4xn      | skupiny po 4 se seradi pomoci sort4, pak listMerge
| 8 Xhybrid_InsertM_ListMerge_m1x_32xn  | skupiny po 32 se seradi pomoci insert-middle, listMerge
| 9 Xhybrid_InsertM_ListMerge_m2_32xn   |
+---------------------------------------+
To jsou dva algoritmy v jednom. 



+---------------------------------------+
| 11 sortInsert_m1_v1_Top               |    
| 12 sortInsert_m1_v2_Top               |    
| 10 sortInsert_m1_v3_Middle (binary)   |    
+---------------------------------------+

Mame prazdne serazene pole a do nej budeme postupne vkladat kazdy prvek z inputu.
Porovnavat budeme vzdy zhora (dokud je druhy prvek vetsi, pokud chcete stabilni sort).
(pro stejne prvky by asi bylo vyhodnejsi porovnavat input zezadu)

(1)     =

(2)     =
       ===

(3)     =
       ===
      =====

(4, 5, 6, 7, 8)
        =
       ===
      =====
     =======

    =========

   ===========

  =============

 ===============


insert-top - porovnava od zacatku out
                   | insert-middle - porovnava od stredu casti out (vyhodne od 32 prvku a vice)
                   |
3 1 2 2 0 3 1 0    | 3 1 2 2 0 3 1 0    // input
out      inp       | out    inp                 
3 <-     3         | 3 <-   3                   
                   |                            
3 <-     1         | 3 <-   1                   
                   |                            
1 <-     2         | 1 <-   2                   
3 <--              | 3 <--  
                   |                            
1 <-     2         | 1                         
2 <--              | 2 <-   2                  
3 <---             | 3 <--                     
                   |                            
1 <-     0         | 1 <---                    
2                  | 2 <--                         
2                  | 2 <-   0                      
3                  | 3                          
                   |                            
0 <-     3         | 0 
1 <--              | 1 
2 <---             | 2 <-   3                    
2 <----            | 2 <--                     
3 <----- ... cmp=5 | 3 <--- .... cmp=3
                   |                            
0 <-     1         | 0 
1 <--              | 1 <---  
2                  | 2 <--                       
2                  | 2 <-   1
3                  | 3 
3                  | 3 

| 10 sortInsert_m1_v3_Middle (binary)   |    

3 1 2 2 0 3 1 0    // input

3                  // is first sorted array, (left = 0), half = 0, mid = 0 + floor(half / 2) (first pos_b), ''' cmp = 0 '''
. 1                // next i = 1, value = array[i] = 1, mid = 0
3-1                // compare 3-1
1 3                // 13 is now output, half = i, mid = 0 + floor(half / 2), ''' cmp + 1 ''' 
.
.   2              // next i, array[i], mid = 0
1---2              // compare(array[i], array[mid]), compare>0, half = floor(half / 2), left = mid, mid = left + half
  2-3              // compare(array[i], array[mid]), compare<0, end (because half = 0, cannot more divide), half = i, mid = 0 + round(half / 2), ''' cmp + 2 ''' 
1 2 3
  .                // ... note: for simplify, i remove lot of repeating text
      2            // next i, mid = 1
  2---2            // compare>0, mid = left + half
  . 3-2            // compare<0, end, ''' cmp + 2 '''
1 2 2 3
  .
  .     0          // next i, mid = 1
  2-----0          // compare<0, mid = left - half
1-------0          // compare<0, end, ''' cmp + 2 '''
0 1 2 2 3
    .
          3        // next i, mid = 2
    2-----3        // compare>0, mid = left + half
    . 2---3        // compare>0, mid = left + half
    .   3-3        // compare<0, end, ''' cmp + 3 '''
0 1 2 2 3 3
    .
    .       1      // next i, mid = 2
    2-------1      // compare<0, mid = left - half
  1---------1      // compare<0, mid = left - half
0-----------1      // compare>0, end, ''' cmp + 3 '''
0 1 1 2 2 3 3
      .
              0    // next i, mid = 3
      2-------0    // compare<0, mid = left - half
  1-----------0    // compare<0, mid = left - half
0-------------0    // compare>0, end, ''' cmp + 3 '''
===============
0 0 1 1 2 2 3 3    // output, suma(cmp) = 1+2+2+2+3+3+3 = 16



+---------------------------------------+
| 19 sortSelect_m1_v1                   |
| 20 XsortSelect_m1_v2                  | - modifikace, kdy si pamatuji prvni swap (-0 az -17% cmp)
| 21 XsortSelect_m1_v3                  | - modifikace, kdy si pamatuji vsechny swap (-0 az -21% cmp)
| 22 XsortSelectPyramid_m3_v1           | - tournament sort (postupova tabulka vitezu na turnaji, pavouk)
+---------------------------------------+

(1) = = = = = = = =		// vyber min z pole a dej ho na pozici 0 (zacatek)
(2)   = = = = = = =		// vyber min z pole a dej ho na pozici 1
(3)     = = = = = =		// vyber min z pole a dej ho na pozici 2
          = = = = =
            = = = =
              = = =
                = =

  19 sortSelect_m1_v1                   
-----------------------------------------

3 1 2 2 0 3 1 0		// min je na i, i=0, a=i, b=i (i, a, b jsou indexy-pozice v poli), cmp = 0
3-1			// b++, array[a=0]>array[b=1], "a" se zmeni a=b=1
  1-2                   // b++, array[a=1]<=array[b=2], "a" se nemeni
  1---2                 // b++, array[a=1]<=array[b=3]
  1-----0               // b++, array[a=1]>array[b=4], "a" se zmeni a=b=4
        0-3             // b++, array[a=4]<=array[b=5]
        0---1           // ...
        0-----0         // ...
0 1 2 2 3 3 1 0		// swap(array[i=0], array[a=4]), i++ (1), a=i, b=i, cmp + 7
  1-2                   // b++, array[a=1]<=array[b=2]
  1---2
  1-----3
  1-------3
  1---------1
  1-----------0         // b++, array[a=1]>array[b=7], "a" se zmeni a=b=7
0 0 2 2 3 3 1 1		// swap(array[i=1], array[a=7]), i++ (2), cmp + 6
    2-2
    2---3
    2-----3
    2-------1           // b++, array[a=2]>array[b=6], "a" se zmeni a=b=6
            1-1
0 0 1 2 3 3 2 1		// swap(array[i=2], array[a=6]), i++ (3), cmp + 5
      2-3
      2---3
      2-----2
      2-------1         // a=7
0 0 1 1 3 3 2 2		// swap(array[i=3], array[a=7]), i++ (4), cmp + 4
        3-3
        3---2           // a=6
            2-2
0 0 1 1 2 3 3 2		// swap(array[i=4], array[a=6]), i++ (5), cmp + 3
          3-3
          3---2         // a=7
0 0 1 1 2 2 3 3		// cmp + 2
            3-3         // cmp + 1
0 0 1 1 2 2 3 3         // output, suma(cmp) = 7+6+5+4+3+2+1 = 28 ... suma = n/2 * (n+1) = 7/2 * (7+1) = 7*8/2 = 28



  22 XsortSelectPyramid_m3_v1             - tournament sort (postupova tabulka vitezu na turnaji, pavouk)
-----------------------------------------

pavel vs. tomas    zdenek vs. michal  --- zapasy prvniho kola
  |         |         |         |
  +----+----+         +----+----+
       |                   |
     tomas               zdenek       --- zapasy druheho kola
       |                   |
       +---------+---------+
                 |
               zdenek                 --- a vitezem se stava zdenek, zdenek tedy odchazi (v zapasech by mel druhe misto tomas, ale u sortu to tak nejde :) )

poradi: zdenek, ?, ?, ?

pavel vs. tomas       -       michal  --- ted je nutne odchoziho nahradit ve vsech jeho zapasech od prvniho kola
  |         |         |         |     --- a zjistit v nich viteze
  +----+----+         +----+----+
       |                   |
     tomas               michal
       |                   |
       +---------+---------+
                 |
               tomas

poradi: zdenek, tomas, ?, ?

pavel       -         -       michal
  |         |         |         |
  +----+----+         +----+----+
       |                   |
     pavel               michal
       |                   |
       +---------+---------+
                 |
               pavel

poradi: zdenek, tomas, pavel, michal

3 1 2 2 0 3 1 0    // input

3-1 2-2 0-3 1-0    // compare pair from input and create level 1 of minimal
  1-2   0-----0    // new level 1 pyramid of index (for code i use index, for scheme i use value)
  1-----0 . .      // new level 2
        0 . .      // new level 3, save "0", cmp = 7
          . .
  1 2     3---0    // rebuild pyramid branch (select second value from input)
  1-----------0
            . 0    // save "0", cmp + 2
            . x
  1 2     3-1 x    // rebuild pyramid branch
  1---------1
  1                // save "1", cmp + 2
  x
3---2     3 1      // rebuild pyramid branch
    2-------1
            1      // save "1", cmp + 2
            x
3   2     3 x      // rebuild pyramid branch (when not even or odd value from input, use "x" (or -1), when "x" copy second index to next level)
    2-----3
    2              // save "2", cmp + 1
    x
3-----2   3        // rebuild pyramid branch (when -1, copy index to next level)
      2---3
      2            // save "2", cmp + 2
      x
3     x   3        // rebuild pyramid (when -1, copy index to next level)
3---------3
3                  // save "3", cmp + 1

          3        // save last "3"
===============
0 0 1 1 2 2 3 3    // output, suma(cmp) = 7+2+2+1+2+2+1 = 17



+---------------------------------------+
| 13 sortCountingPigeonhole_mx_v1       | - vyhodne pro pole integer
| 14 sortCountingRadixLSB_mx_v2         | - vyhodne pro male integer, float a jine binarni pole
| 15 sortCountingRadixLSD_mx_v3         | - vyhodne pro posle stringu
| 16 sortCountingRadixLSD_mx_v4         | 
+---------------------------------------+


  13 sortCountingPigeonhole_mx_v1         - vyhodne pro pole integer
-----------------------------------------

Spocitaji pocet opakovani stejnych hodnot. A pak vypise podle opakovani.
Vyuziva toho, ze cislovane pole se prochazi cyklem od 0 do value-max, zname tedy min a max hodnotu pole.

3 1 2 2 0 3 1 0

1) = 2x   === 2x   ===== 2x   ======= 2x    --- spocitam opakujici se prvky (cyklus 0 az value-max, nektere maji pocet opakovani 0)
   =      ===      =====      =======

2)      =                                   --- vypisu vsechny prvky, opakovane vypiso v poctu opakovani (cyklus 0 az value-max)
        =  
       === 
       === 
      =====
      =====
     =======
     =======


3 1 2 2 0 3 1 0    // input

hodnota=0, pocet=2x
hodnota=1, pocet=2x
hodnota=2, pocet=2x
hodnota=3, pocet=2x

00 11 22 33  --- vypis 2x hodnotu=0, vypis 2x hodnotu=1, ...


  15 sortCountingRadixLSD_mx_v3           - vyhodne pro posle stringu
-----------------------------------------

Roztrid podle prvni cislice (low-sort-digit) na levou a pravou stranu. Zapis. Opakuj pro dalsi cislici.

  3   1    2    2    0    3    1    0    // input
003 001  002  002  000  003  001  000 (2 = dec 2, pos je pocitano od konce, pro ukazku volim 3 cislice, ale jinak by se pocitalo asi s jednou)

pos=0, digit==0, cisla = 0 0 --- roztrid
pos=0, digit==1, cisla = 1 1
pos=0, digit==2, cisla = 2 2
pos=0, digit==3, cisla = 3 3
0 0 1 1 2 2 3 3              --- zapis
pos=1, digit==0, cisla = 0 0 1 1 2 2 3 3 --- znovu roztrid
pos=0, digit==1, cisla = 
pos=0, digit==2, cisla = 
pos=0, digit==3, cisla = 
0 0 1 1 2 2 3 3
pos=2, digit==0, cisla = 0 0 1 1 2 2 3 3 --- znovu roztrid
pos=0, digit==1, cisla = 
pos=0, digit==2, cisla = 
pos=0, digit==3, cisla = 
0 0 1 1 2 2 3 3


  14 sortCountingRadixLSB_mx_v2           - vyhodne pro male binarni pole
-----------------------------------------

Rozdel cisla podle prvniho bitu (low-sort-bit) na levou a pravou stranu. Zapis. Opakuj pro dalsi bit

3  1  2  2  0  3  1  0    // input
11 01 10 10 00 11 01 00 (2 = bin 00000010 nebo 10, pos je pocitano od konce)

pos=0, bit==0, cisla = 2 2 0 0 --- roztrid
pos=0, bit==1, cisla = 3 1 3 1 
2 2 0 0 3 1 3 1                --- zapis
pos=1, bit==0, cisla = 0 0 1 1 --- znovu roztrid
pos=1, bit==1, cisla = 2 2 3 3
0 0 1 1 2 2 3 3







+---------------------------------------+
| 30 sortBubblingBubble_m1_v1           | 
| 31 sortBubblingBubble_m1_v2           | 
| 32 sortBubblingBubble_m1_v3_cocktail  | - coctail-shaker
| 34 sortBubblingQuick_m1x_v2           | 
| 35 sortBubblingQuick_rnd_m1x_v3       | 
| 37 sortBubblingQuick_rnd_stable_m2x_v4| 
+---------------------------------------+

  30 sortBubblingBubble_m1_v1            - postupne posunuje nejvetsi hodnotu na konec
-----------------------------------------

3 1 2 2 0 3 1 0
3-1
1 3                // swap, zamen, aby mensi byla pred vetsi
. 3-2
. 2 3              // swap
. . 3-2
. . 2 3
. . . 3-0
. . . 0 3
. . . . 3-3
. . . . . 3-1
. . . . . 1 3
. . . . . . 3-0   // cmp + 7
. . . . . . 0 3
1 2 2 0 3 1 0 3   // out
1-2
  2-2
    2-0
    0 2-3
        3-1
        1 3-0     // cmp + 6
          0 3  
1 2 0 2 1 0 3 3   // out
1-2
  2-0
  0 2-2
      2-1
      1 2-0       // cmp + 5
        0 2
1 0 2 1 0 2 3 3   // out
1-0
0 1-2
    2-1
    1 2-0         // cmp + 4
      0 2
0 1 1 0 2 2 3 3   // out
0-1-0-1 2 2 3 3   // out cmp + 3
0-0-1 1 2 2 3 3   // out cmp + 2
0-0 1 1 2 2 3 3   // out cmp + 1
0 0 1 1 2 2 3 3   // output, suma(cmp) = 7+6+5+4+3+2+1 = 28 ... suma = n/2 * (n+1) = 7/2 * (7+1) = 28


  32 sortBubblingBubble_m1_v3_cocktail   - oboustranny bubble, bubla se z obou stran, dokud dojde ke swapovani
-----------------------------------------
3 1 2 2 0 3 1 0
3-1                // prvni cast je stejna jako bubble
1 3                // . swap, zamen, aby mensi byla pred vetsi
. 3-2              // .
. 2 3              // . swap
. . 3-2            // .
. . 2 3            // . swap
. . . 3-0          // .
. . . 0 3          // . swap
. . . . 3-3        // .
. . . . . 3-1      // .
. . . . . 1 3      // . swap
. . . . . . 3-0    // . ... cmp + 7
. . . . . . 0 3    // . swap
1 2 2 0 3 1 0 3    // . out, max je na konci. Pak se postupuje z opacne strany,
              .    // a pak to cele opakuj, dokud behem cyklu dojde k aspon 1 swapu
              .    // pozn: tady budu swapy vypisovat, protoze cekame, az zadny nenastane
              .    // pozn: pripomina to michani koktejlu v shakeru
1 2 2 0 3 1 0 3
          1-0 .
        3-0 1 .
        0 3   .    // swap
      0-0     .
    2-0       .
  2-0 2       .    // swap
1-0 2         .    // swap
0 1           .    // swap
0 1 2 2 0 3 1 3    // out, min je na zacatku ... cmp + 6
. 1-2         .
.   2-2       .
.     2-0     .
.     0 2-3   .    // swap
.         3-1 .
          1 3 .    // swap
0 1 2 0 2 1 3 3    // out ... cmp + 5
.       2-1 . .
.     0-1 2 . .    // swap
.   2-0     . .
. 1-0 2     . .    // swap
. 0 1       . .    // swap
0 0 1 2 1 2 3 3    // out ... cmp + 4
. . 1-2     . .    
. .   2-1   . .
. .   1 2-2 . .    // swap
0 0 1 1 2 2 3 3    // out ... cmp + 3
. .   1-2 . . .
. . 1-1   . . .    // cmp + 2, nedoslo ke swapu, konec
0 0 1 1 2 2 3 3    // output, suma(cmp) = 7+6+5+4+3+2 = 27 (zadna slava, ale pro vic cisel se jedna asi o 21% usporu)


  34 sortBubblingQuick_m1x_v2            - zvoli se pivot, obvykle uprostred pole, pak se najde zleva prvni vetsi cislo, zprava prvni mensi a vymeni se
-----------------------------------------
3 1 2 [2] 0 3 1  0       // pivot volim na pivot_pos=2, hodnota=2, left=0, right=n
3 1 2     0 3 1  0       // pivota jakoby odstran
                       
3------2                 // arr[left]>arr[pivot], stop, cislo vlevo je vetsi nez pivot, zacni porovnavat z opacne strany
       2---------0       // arr[pivot]<=arr[right], stop, cislo vpravo je mensi nez pivot
0                3       // swap
  1----2                 // najdi dalsi cislo zleva vetsi nez pivot
    2--2                 
       2--0              
       2----3            // stop, nasel cislo vetsi nez pivot pri hledani zleva, hledej cislo zprava
       2------1          // stop, nasel cislo mensi nez pivot pri hledani zprava
            1 3          // swap
             2           // vloz zpet pivota za posledni nalezenou pozici zleva ... cmp + 7
0 1 2     0 123  3       // out, rozdel podle novych pivotu levou i pravou stranu o posledni pivota
0 1 2 0 1   |2|  3  3
0 1 (2) 0 1 |2| [3] 3    // novy pivot pro levou cast je (2), novy pivot pro pravou cast je [3], kazdou cast zpracuji zvlast
0----2                   // cast1
  1--2                  
     2--0                
     2----1              // cast1: nenasel zadne cislo zleva vetsi nez pivot, zapis, dej pivota nakonec ... cmp + 4
0 1  0 1 (2)|2|  3  3   
                 3--3    // cast2: take nenasel cislo zleva ... cmp + 1
0 (1) 0 1 | 2  2 3  3    // pokracuj dalsi sub-casti1 z casti1, ostatni jsou jiz hotove
0--1                     // sub-cast1:
   1--0                  // sub-cast1: zleva nasel
   1----1                // sub-cast1: zprava nenasel, takze pivot umisti za posledni leve ... cmp + 3
0  0 (1)1   2  2 3  3    // sub-cast2: ma jeden prvek, tam je hotovo, urci dalsi sub-sub-casti a pivoty
0 (0) | 1 1 2  2 3  3    // sub-cast2: ma jeden prvek, tam je hotovo, urci dalsi sub-sub-cast
0--0                     // nenasel, nejsou dalsi casti, sub-casti, sub-sub-casti, konec ... cmp + 1
0 0 1 1 2 2 3 3          // output, suma(cmp) = 7+4+1+3+1 = 15