Pro algoritmus sorted-list-merging pro delku pole v nasobcih dvou plati:

n = 256 = 2^8
On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1)
On = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128)
On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128)   | 1+2+4... = geometricka posloupnost Sn = a1 * (q^i - 1) / (n - 1), n je pocet prvku, a1 je prvni prvek
On = 8*n - 1 * (2^8 - 1) / (2 - 1)
On = 8*n - (2^8 - 1)   | 2^8 = n
On = 8*n - (n - 1)
On = (8-1)*n + 1   | 8 = ln(n)/ln(2) = ln(256)/ln(2)
On = (ln(n)/ln(2) - 1) * n + 1

Pak je mozne odhadnout slozitost, ke ktere ma algoritmus dospet.
Stale lepsi nez fiktivni hodnota O(n log n) :)

---

n = 8 = 2^3 (3 = ln(n)/ln(2))
(1) = = = = = = = =		

(2) =   =   =   =               // pri spojovani 1-1, nejhorsi pripad je 1 porovnani, opakovani 4x
   === === === ===              // (sizeA=1 + sizeB=1 - 1)

(3)   =       =                 // pri spojovani 2-2, nejhorsi pripad je 3 porovnani, opakovani 2x
     ===     ===                // (sizeA=2 + sizeB=2 - 1)
    =====   ===== 
   ======= =======

(4)                             // pri spojovani 4-4, nejhorsi pripad je 7 porovnani, opakovani 1x
                                // (sizeA=4 + sizeB=4 - 1)

On = 4*(2-1) + 2*(4-1) + 1*(8-1) = 4 + 6 + 7 = ___17___
On = (ln(n)/ln(2) - 1) * n + 1 = (3 - 1) * 8 + 1 = 16 + 1 = ___17___

---

Pro délku pole v násobcích dvou platí:

:<math>O(n \log n) = (\ln(n) / \ln(2) - 1) * n + 1</math>

Pro představu, jaký je rozdíl mezi řazením 1 000 prvků a 1 000 000 prvků:

:<math>n = 2^4 = 16, O(n \log n) = 49 (3*16+1)</math>
:<math>n = 2^8 = 256, O(n \log n) = 1.793 (7*256+1)</math>
:<math>n = 2^10 = 1.024, O(n \log n) = 9.217 (9*1024+1)</math>
:<math>n = 2^20 = 1.048.576, O(n \log n) = 19.922.945 (19*1048576+1)</math>

n = 2^4 = 16, On ~= 3*n
n = 2^8 = 256, On ~= 7*n
n = 2^10 = 1.024, On ~= 9*n
n = 2^20 = 1.048.576, On ~= 19*n