Bloksort

Bloksort

Bloksort stabilno sortiranje brojeva od 1 do 16. Sortiranje umetanjem grupe od 16, izbacuje dva unutrašnja bafera, označava A blokove (svaki veličine √16 = 4 ), rola A blokove kroz B, lokalno ih spaja, sortira drugi bafer, i prepraspoređuje bafere.
Klasa	Algoritmi sortiranja
Struktura podataka	Niz
Najgora performanca	$O(n\log n)$
Najbolja performanca	$O(n)$
Prosečna performanca	$O(n\log n)$
Najgora prostorna kompleksnost	$O(1)$

Bloksort, je algoritam sortiranja koji spada u grupu stabilnih algoritama sortiranja, i sastoji se od najmanje dve operacije spajanja i od sortiranja umetanjem u O(nlogn) vremenu u mestu. Naziv je dobio iz zaključka da spajanje dve sortirane liste, A i B, je ekvivalentno deljenju A u blokove jednakih veličina, i ubacivanje svakog bloka A u listu B pod specijalnim uslovima, i spajanje AB para.

Jedan praktičan algoritam za bloksort su predložili Pok-Son Kim i Arne Kutzner 2008. godine.

Pregled

Spoljašnja petlja bloksorta je identična algoritmu sortiranja spajanjem sa implementacijom odozdo-nagore, gde svaki nivo sortiranja spaja parove podnizova, A i B, u veličinama od 1, zatim 2, pa 4, 8, 16, i tako dalje, sve dok oba podniza ne budu postali jedan niz.

Umesto spajanja A i B tradicionalnom metodom, algoritam spajanja sa blokovima deli A u odvojene blokove veličina √A (što daje √A blokova), ubacuje se svaki blok A u B tako da prva vrednosta svakog bloka A bude manja ili jednaka od vrednosti B, lokalno spaja svaki blok A sa bilo kojom vrednošću između B bloka i sledećeg A bloka. Pošto spajanje i dalje zahteva dovoljno veliki bafer da može da prihvati blok A koji se spaja, dva dela u nizu su rezervisana za ovu svrhu (poznatiji kao interni tj unutrašnji baferi). Prva dva A bloka su zato modifikovana da sadrže prvu instancu svake vrednosti iz A, sa pravim sadržajem ovih blokova koji se pomeraju (šiftuju) ako je neophodno. Preostali A blok se onda umeće u B i spaja se pomuću jednog od dva bafera koji služe kao prostor zamene. Zbog ovog procesa, vrednost u tom baferu se mora preurediti.

Jednom kad se svaki A i B blok svakog A i B podniza spoje za taj nivo sortiranja spajanjem, onda se vrednosti u tom baferu mogu sortirati da bi povratili svoje prvobitno uredjenje (poredak), pa se sortiranje umetanjem mora iskoristiti. Vrednosti u baferima se raspodeljuju prema njihovim prvim sortiranim pozicijama u nizu. Ovaj proces se ponavlja za svaki nivo sortiranja spajanjem (spoljašnja odozdo nagore implementacija), i u tom trenutku niz će biti stabilno sortiran.

Algoritam

Sledeći operatori se koriste u primeru koda:

|	inkluzivno ili
>>	šiftovanje udesno
%	modulo
++ i +=	inkrement
[x, y)	raspon od ≥ x i < y
|raspon|	raspon.kraj - raspon.početak
niz[i]	element niza

Takođe, bloksort koristi sledeće operacije kao deo algoritma:

• Zamena: menja pozicije dve vrednosti u nizu.
• Blok zamena: menja raspon vrednosti u nizu sa vrednostima u drugom rasponu niza.
• Binarna pretraga: pretpostavljamo da je niz sortiran, proverava srednju vrednost trenutnog opsega, zatim ako je vrednost manja proverava donji raspon, a ako je veća proverava gornji raspon. Bloksort koristi dve varijante: jedna koja pronalazi prvu poziciju za ubacivanje u sortirani niz, i drugu varijantu koja pronalazi poslednju poziciju.
• Linearna pretraga: traži određenu vrednost u nizu proveravajući svaki element u poretku, sve dok ga ne nađe.
• Sortiranje umetanjem: za svaki element u nizu, prolazi kroz petlju od pozadi i traži gde treba da se ubaci element, a zatim ga i stavi na tu poziciju.
• Rotiranje niza: pomeranje elemenata niza ulevo ili desno nekim brojem razmaka, vrednostima sa krajeva niza. Rotacja može biti implementirana kao okretanje stabla.

   Rotiraj(niz, kolicina, raspon)
       Obrni(niz, raspon)
       Obrni(niz, [raspon.pocetak, raspon.pocetak + kolicina))
       Obrni(niz, [raspon.pocetak + kolicina, raspon.kraj))

• Najveći ceo broj stepena 2: je seldeća vrednost stepena 2. 63 postaje 32, 64 ostaje 64, itd.

   CeoBrojStepenaDva(x)
       x = x | (x >> 1)
       x = x | (x >> 2)
       x = x | (x >> 4)
       x = x | (x >> 8)
       x = x | (x >> 16)
       if (ovo je 64-bitni sistem)
           x = x | (x >> 32)
       return x - (x >> 1)

Spoljašnja petlja

Kao što smo naveli, spoljašnja petlja Bloksorta je identična kao implementacija odozdo-nagore sortiranja spajanjem.

   BlokSort(niz)
       stepen_dvojke = CeoBrojStepenaDva(niz.size)
       skala = niz.size/stepen_dvojke // 1.0 ≤ skala < 2.0
      
       // sortiranje umetanjem 16-31 elementa odjednom
       for (spajanje = 0; spajanje < stepen_dvojke; spajanje = spajanje + 16)
           pocetak = spajanje * skala 
           kraj = (spajanje + 16) * skala 
           SortiranjeUmetanjem(niz, [pocetak, kraj))
      
       for (duzina = 16; duzina < stepen_dvojke; duzina = duzina * 2)
           for (spajanje = 0; spajanje < stepen_dvojke; spajanje = spajanje + duzina * 2)
               pocetak = spajanje * skala 
               sred = (spajanje + duzina) * skala 
               kraj = (spajanje + duzina * 2) * skala 
              
               if (niz[kraj- 1] < niz[pocetak])
                   // dva intervala su u obrnutom redosledu, tako da je rotacija dovoljna da ih spoji. 
                   Rotiraj(niz, sred - pocetak, [pocetak, kraj))
               else if (niz[sred- 1] > niz[sred])
                   Spoji(niz, A = [pocetak, sred), B = [sred, kraj))

Fiksirani broj cifara se takođe može koristiti, prikazivanjem faktor skaliranja kao razlomak:

   stepen_dvojke = CeoBrojStepenaDva(niz.size)
   delilac = stepen_dvojke/16
   deljenik_korak = niz.size % delilac 
   dec_korak = sprat(niz.size/delilac)
  
   [sortiranje umetanjem 16-31 elemenata odjednom]
  
   while (dec_korak < niz.size)
       decimal = deljenik = 0
       while (decimal < niz.size)
           // uzima opseg od A do B
           pocetak = decimal
          
           decimal += dec_korak
           deljenik += deljenik_korak
           if (deljenik ≥ delilac)
               deljenik -= delilac
               decimal++
          
           sred = decimal
          
           decimal += dec_korak
           deljenik += deljenik_korak
           if (deljenik ≥ delilac)
               deljenik -= delilac
               decimal++
          
           kraj = decimal
          
           if (niz[kraj - 1] < niz[pocetak])
               Rotiraj(niz, sred - pocetak, [pocetak, kraj))
           else if (niz[mid - 1] > niz[sred])
               Spoji(niz, A = [pocetak, sred), B = [sred, kraj))
      
      deljenik_korak += deljenik_korak
      dec_korak += dec_korak
       if deljenik_korak ≥ delilac)
           deljenik_korak -= delilac
           dec_korak++

Izdvajanje bafera

Proces izbacivanja bafera u bloksortu.

Dva unutrašnja bafera koja su neophodna za svaki nivo spajanja se kreiraju pomeranjem prvih 2√A instanci svake vrednosti unutar jednog podniza A sa početkom A. Algoritam prvo iterira kroz elemente u A i prebrojava jedinstvene vrednosti koje mu trebaju, zatim rotira niz da bi pomerio ove jedinstvene vrednosti na pocetak. Ako A nije sadržao dovoljno jedinstvenih vrednosti da popuni dva bafera (iste veličine √A ), B može isto tako dobro da se koristi. U ovom slučaju pomera se poslednja instanca svake vrednosti do kraja B, sa preostalim B delom koji nije bio uključen tokom spajanja.

   while (decimal_korak < niz.size)
       blok_velicina = √decimal_korak
       velicina = decimal_korak/blok_velicina + 1
       [izbacuje dva bafera veličine 'bafer_size']

Ako B ne sadrži dovoljno jedinstvenih vrednosti, izbacuje se broj sa najvećom jedinstvenom vrednošću koja je mogla da se pronađe, zatim podesi veličinu A i B bloka tako da broj rezultujućih A blokova je manji ili jednak broju izbačenih elemenata (ubačenih na bafer). Samo će se jedan bafer koristiti u ovom slučaju – drugi bafer neće ni postojati.

   bafer_velicina = [pronađeni broj vrednosti]
   blok_velicina = decimal_korak/bafer_velicina + 1
  
   decimal = deljenik = 0
   while (decimal < niz.size)
       [uzima intervale od A i B]
       [podešava A i B da ne koriste intervale koje koriste baferi]

Označavanje blokova

Označavanje A blokova pomoću vrednosti iz prvog unutrašnjeg bafera. Primetite da su prvi A blok i poslednji B blok različitih veličina.

Jednom kada se jedan ili dva unutrašnja bafera naprave, započinje se spajanje svakog A i B podniza za ovaj nivo sortiranja spajanjem. Da bi se desilo sve to, svaki A i B podniz se deli na jednake blokove jednakih veličina, koje su izračunate u prethodnom koraku, gde su prvi A blok i poslednji B blok bili različitih veličina (ako je bilo potrebno). Zatim se krece kroz petlju za svaki A blok i zameni drugu vrednost sa odgovarajućom vrednošću iz prvog unutrašnjeg bafera. Ovo se naziva označavanje blokova.

   // blokA je interval preostalih A blokova,
   // i prviA je A blok druge veličine
   blokA = [A.pocetak, A.pocetak  + |blokA| % blok_velicina)
  
   // zameni drugu vrednost svakog A bloka sa vrednošću u bafer1
   for (index = 0, indexA = firstA.kraj + 1; indexA < blokA.kraj; indexA += blok_velicina)
       Zameni(niz[bafer1.pocetak + index], niz[indexA])
       index++
  
   poslednjiA = prviA
   blokB = [B.poceetak, B.pocetak + minimum(blok_velicina, |B|))
   blokA.pocetak += |prviA|

Rolovanje i izbacivanje

Dva A bloka se rolaju kroz B blokove. Jednom kada se prvi A blo izbaci iza, blok A razlicite velicine se lokalno spaja sa odgovarajucim B vrednostima.

Posle definisanja i označavanje A blokova , A blokovi su urolani (uvijeni) u B blokove zamenom prvog A bloka sa sledećim B blokom. Ovaj proces se ponavlja sve dok je prva vrednost A bloka sa najmanjom označenom vrednošću manja ili jednaka poslednjoj vrednosti B bloka-koja je upravo zamenjena sa A blokom.

U tom trenutku, najmanji A blok (A blok sa najmanjom označenom vrednošću) je zamenjen na početak rolovanja A blokova a označena vrednost postaje prvobitna vrednost iz prvog bafera. Ovo se naziva izbacivanje bloka iza, pošto se neće više rolovati sa preostalim A blokovima. Zatim se A blok umeće u prethodni B blok, prvo se koristi binarna pretraga na B da bi se našlo indeks gde je prva vrednost A manja ili jednaka elementu tog indeksa od B, i zatim na tom indeksu rotiramo A u B.

   minA = blokA.pocetak
   indexA = 0
  
   while (true)
       // ako postoji prethodni B blok i prva vrednost minimuma A bloka je ≤
       // poslednja vrednost prethodnog B bloka, onda izbaci iza taj minimum A bloka.
       // ili ako nema preostalih B blokova onda nastavi da izbacujes preostaleA blokove.
       if ((|poslednjiB| > 0 and niz[poslednjiB.kraj - 1] ≥ niz[minA]) or |blokB| = 0)
           // pronaći gde da se podeli prethodni B blok, i rotirati ga oko sredine
           B_rascepljenje = BinarnaPrva(niz, niz[minA], lastB)
           B_ostatak = poslednjiB.kraj - B_rascepljenje
          
           // Zameni minimum A bloka na početak rolanja A blokova
           blokZamena(niz, blokA.pocetak, minA, blok_velicina)
          
           // vraća drugu vrednost za blok A
           Zameni(niz[blokA.pocetak + 1], niz[bafer1.pocetak + indexA])
           indexA++
          
           // rotira blok A oko prethodnog B bloka
           Rotiraj(niz, blokA.pocetak - B_rascepljenje, [B_rascepljenje, blokA.pocetak + blok_velicina))
          
           // lokalno spajanje prethodnog A loka sa B vrednostima,
           // koristeći drugi unutrašnji bafer kao prostor za zamenu (ako postoji)
           if (|bafer2| > 0)
               SpajanjeUnutrasnje(niz, poslednjiA, [poslednjiA.kraj, B_rascepljenje), bafer2)
           else
               SpajanjeUMestu(niz, lastA, [poslednjiA.kraj, B_rascepljenje))
          
           // ažuriraj raspon za preostale A blokove,
           // i preostali raspon od B se posle deli
           poslednjiA = [blokA.pocetak - B_ostatak, blokA.pocetak - B_ostatak + blok_velicina)
           poslenjiB = [poslednjiA.kraj, poslednjiA.kraj + B_ostatak)
          
           // ako ne postoji više preostalih A blokova, ovaj korak je završen onda
           blokA.pocetak = blokA.pocetak + blok_velicina
           if (|blokA| = 0)
               break
          
           minA = [novi minimum A bloka] (pogledaj ispod)
       else if (|blokB| < blok_velicina)
           // pomeranje poslednjeg B bloka, koji je druge veličine,
           // do prethodno preostalih A blokova pomoću rotacije
           Rotiraj(niz, blokB.pocetak - blokA.pocetak, [blokA.pocetak, blokB.kraj))
          
           poslednjiB = [blokA.pocetak, blokA.pocetak + |blokB|)
           blokA.pocetak += |blokB

| blokA.kraj += |blokB | minA += |blokB | blokB.kraj = blokB.pocetak

       else
           // rolanje skroz levog A bloka na kraj pomoću zamene sa sledećim B blokom
           blokZamena(niz, blokA.pocetak, blokB.pocetak, blok_velicina)
           poslednjiB = [blokA.pocetak, blokA.pocetak + blok_velicina)
           if (minA = blokA.pocetak)
               minA = blokA.kraj
          
           blokA.pocetak += blok_velicina
           blokA.kraj += blok_velicina
           blokB.pocetak += blok_velicina
          
           // ovo je ekvivalentno minimumu' (blokB.kraj + blok_size, B.kraj),
           // ali ima potenciju da ima prekoračenje 
           if (blokB.kraj > B.kraj - blok_velicina)
               blokB.kraj = B.kraj
           else
               blokB.kraj += blok_velicina
  
   // spajanje poslednjeg A bloka sa preostalim B vrednostima
   if (|bafer2| > 0)
       SpajanjeUnutrasnje(niz, poslednjiA, [poslednjiA.kraj, B.kraj), bafer2)
   else
       SpajanjeUMestu(niz, poslednjiA, [poslednjiA.kraj, B.kraj))

Tokom ovog koraka može se primeniti optimizacija zvana tehnika pokretne-rupe. Kada se najmanji (minimum) A blok izbaci onda je neophodno ga je rotirati u prethodnom B bloku, posle čega se njegov sadržaj menju u drugi unutrašnji bafer za lokalno spajanje, a bilo bi brže da se A blok zameni u baferu unapred, i iskoristi prednost da sadržaji bafera ne moraju ostati u poretku. Pa umesto rotiranja drugog bafera (koji je pre zamene bio A blok) u prethodnu B blok poziciju indeksa, bolje je vrednosti B bloka posle indeks jednostavno zameniti sa poslednjim elementima bafera.

U ovom slučaju Pokretnu rupa se odnosi na sadržaj drugog unutrašnjeg pokretnog bafera koji je oko niza, i ponaša se kao rupa u smislu da elementi ne moraju da održe poredak.

Lokalno spajanje

Kada se jednom A blok rotira u B blok, onda je prethodni A blok spaja sa odgovarajućim B vrednostima, c koristeći drugi bafer kao pomoćni za zamenu. Kada se prvi A blok izbaci iza to ukazuje da je A blok različite veličine na početku, kada se drugi A blok izbaci iza to znači da je prvi A blok, i tako dalje.

   SpajanjeUnutrasnje(niz, A, B, bafer)
       // blok zamena vrednosti u A sa vrednostima u 'baferu'
       BlokZamena(niz, A.pocetak, bafer.pocetak, |A|)
      
       A_brojac = 0, B_brojac = 0, ubaci = 0
       while (A_brojac < |A| and B_brojac < |B|)
           if (niz[bafer.pocetak + A_brojac] ≤ niz[B.pocetak + B_brojac])
               Zameni(niz[A.pocetak + ubaci], niz[bafer.pocetak + A_brojac])
               A_brojac++
           else
               Zameni(niz[A.pocetak + ubaci], niz[B.pocetak + B_brojac])
               B_brojac++
           ubaci++
      
       // blok zamena preostalog dela bafera sa preostalim delom niza
       blokZameni(niz, bafer.pocetak + A_brojac, A.pocetak + ubaci, |A| - A_brojac)

Ako ne postoji drugi bafer, onda se mora primenit operacija spajanja u mestu, kao što je verzija bazirana na rotaciji npr. algoritam, the Dudzinski and Dydek algorithm, ili ponavljana binarna pretraga i rotacija.

   SpajanjeUMestu(niz, A, B)
       while (|A| > 0 and |B| > 0)
           // pronalazi prvo mesto u B gde se umeće prvi element u A
           sred = BinarnaPrva(niz, niz[A.pocetak], B)
          
           // rotira A u mestu
           kolicina = sred - A.kraj
           Rotiraj(niz, kolicina, [A.pocetak, sred))
          
           // izračunava nove raspone A i B
           B = [sred, B.kraj)
           A = [A.pocetak + amount, sred)
           A.pocetak = BinarnaPoslednja(niz, niz[A.pocetak], A)

Posle izbacivanja minimuma iz A bloka i spajanja prethodnog A bloka sa odgovarajućim B vrednostima, novi minimum A bloka se mora naći u blokovima koji se još rolaju kroz niz. Ovo se obezbeđuje pokretanjem linearne pretrage kroz ove A blokove i zatim poređenje označenih vrednosti kako bismo našli najmanju vrednost.

   minA = blokA.pocetak
   for (nadjiA = minA + blok_size; nadjiA < blokA.kraj - 1; nadjiA += blok_size)
       if (niz[nadjiA + 1] < niz[minA + 1])
           minA = nadjiA

Preostali A blokovi nastavljaju rolanje kroz niz a oni se izbacuju u ubacuju tamo gde oni treba da budu. Ovaj proces se odvija sve dok svi A blokovi ne budu izbačeni i rotiraniu prethodni B blok.

Kada se jednom izbaci poslednji preostali A blok i ubaci u B blok gde odgovara, onda treba da se spoji sa preostalim B vrednostima. Ovim se završava proces spajanja za određeni par podnizova A i B. Međutim, onda se mora ponoviti proces za preostale podnizove A i B za trenutni nivo sortiranja spajanjem.

Primetite da se unutrašnji baferi mogu iskoristiti za svaki skup podnizova A i B za ovaj nivo sortiranja spajanjem, i ne mora se ponovo izbacivati ili modifikovati u bilo kom smislu.

Preraspodela

Nakon što se spoje nizovi A i B, jedan od spoljašnjih bafera i dalje preostane. Prvi spoljašnji bafer je korišćen za oznaku A blokova, i njegov sadržaj je i dalje ostao u istom poretku, dok je drugi bafer preuredio svoj poredak onda kada je bio korišćen za zamenu zbog spajanja. Ovo znači da se sadržaji drugog bafera moraju sortirati drugim algoritmom, kao što je sortiranje umetanjem. Zatim, ta dva baera se moraju preraspodeliti nazad u niz ali sa obrnutim procesom (obrnut proces u odnosu na njegov nastanak). Algoritam bloksort je gotov posle ponavljanja ovih koraka na svakom nivou implementacije odozdo nagore algoritma-sortiranje spajanjem.

Varijante

Bloksort sa vađenjem dva untrašnja bafera, raybijanje podnizova A i B u blokobe jednakih veličina, rolanje (rol) i ispuštanje A blokova u B (koristeći prvi bafer za praćenje poretka A blokova), lokalno spajanje koristeći drugi bafer kao prostor za zamenu, sortiranje drugog bafera, i preraspodela oba bafera. Dok se koraci ne promene, ovi podsistemi se mogu razlikovati u svojoj implementaciji.

Jedna varijanta bloksorta nam dozvoljava da koristimo bilo koju količinu dodatne memorije, koristeći ovaj spoljašnji bafer za spajanje podniza A ili bloka A sa B uvek kada A može da stane. U ovoj situaciji algoritam bi bio identičan kao algoritam sortiranja spajanjem.

Dobri izbori za veličinu bafera uključuju:

Veličina	Beleške
(brojac + 1)/2	sortiranje spajanja pocinje da radi punom brzinom, pošto će se svi A podnizovi uklopiti
√(brojac + 1)/2 + 1	ovo će biti veličina A blokova na najvećem nivou spajanja, pa bloksort se može preskočiti unutrašnjim ili spajanjem u mestu
512	bafer fiksirane veličine, dovoljno veliki da radi sa raznim spajanjima na manjim nivoima sortiranja spajanjem.
0	ako sistem ne može da izdvoji (alocira) bilo koju dodatnu memoriju, ipak će raditi dobro.

Umesto označavanja A blokova preko sadržaja jednog od unutrašnjih bafera, može se koristiti indirektni pokretni-imitacioni-bafer.Ovo je unutrašnji bafer definisan kao s1 t s2, gde su s1 i s2 iste veličine kao broj A i B blokova, i t sadrži bilo koju vrednost koja prati s1 i jednaka je poslednjoj vrednosti s1 (što potvrđuje da ni jedna vrednost u s2 se ne pojavljuje u s1). Drugi unutrašnji bafer sadrži √A jedinstvenih vrednosti koje se i dalje koriste. Prvih √A vrednosti iz s1 i s2 su zamenjene (jedna drugom) da bi šifrovale informacije u baferu o tome koji blokovi su A blokovi a koji B blokovi. Kada se A blok sa indeksom i zameni B sa blokm indeksa j (gde je prvi A blok inicijalno indeksa 0), s1[i] i s1[j] su zamenjeni sa s2[i] i s2[j]. Ovo imitira pokrete A blokova kroz B. Jedinstvene vrednosti u drugom baferu se koriste da se odredi prvobitan (originalan) poredak A blokova pošto se rolaju kroz B blokove. Kada se jedanput izbace A blokovi, pokretni-imitacioni bafer se koristi da dešifruje da li je dati blok u nizu A blok ili B blok, svaki A blok se rotira u B bloku, i drugi unutrašnji bafer sekoristi kao prostor za zamenu ilokalno spajanje.

Druga vrednost svakog A bloka ne mora da se obavezno znači – prvi, poslednji ili bilo koji drugi element se može koristite umesto. Međutim, a ko je označena prva vrednost, onda će se vrednosti čitati od prvog unutrašnjeg bafera (gde su i zamenjene) prilikom odlučivanja gde da se izbaci najmanji A blok.

Postoji mnogo algoritama koji se mogu koristiti za sortiranje sadržaja drugog unutrašnjeg bafera, uključujući i nestabilno sortiranje kao što je Kviksort, pošto je sadržaj bafera zagarantovano jedinsteven. Sortiranje umetanjem je i dalje preporučeno.

Analiza

Bloksort je dobro definisana i istestirana klasa algoritama, koja dostupnim implementacijama. Ovo omogućava njegovim karakteristikama da se izmere i uzmu u obzir.

Složenost

Bloksort započinje umetanjem grupe od 16-31 elemenata u niz. Sortiranje umetanjem je O(n²) operacija, pa to dovodi od O(16² * n/16) do O(31² * n/31), što je O(n) kada se konstantne vrednosti zanemare. Takođe mora se primeniti sortiranje umetanjem na drugi unutrašnji bafer posle svakog završenog nivoa spajanja. Međutim, pošto je ovaj bafer ograničen na √A veličine, O(√n²) operacija takođe se završava sa O(n).

Zatim se mora izvaditi dva unutrašnja bafera za svaki nivo sortiranja spajanjem. To radi tako što iterira kroz elemente u A i B podnizovima i povećava brojač uvek kada se promeni vrednost, i na nalaženju dovoljno vrednosti da ih rotira na početak A ili na kraju B. U najgorem slučaju će se pretražiti ceo niz pre pronalažena √A nesusednih jedinstvenih vrednosti, što zahteva O(n) poređenja i √A rotacija za √A Vrednosti. Ovo se rešava u O(n + √n * √n), ili O(n).

Kada ni A ni B podnizovi ne sadrže √A jedinstvene vrednosti da naprave unutrašnje bafere, operacija spajanja se odvija u mestu gde se ponavaljano binarno pretražuje i rotira A u B. Međutim, poznati nedostatak jedinstvenih vrednosti u bilo kom podnizu, je ograničenje broja binarnih pretraga i rotacija koje će se desiti tokom ovog koraka, što opet daje √A elemenata rotiranih u √A vremeni, uli O(n). Veličina svakog bloka je takođe podešena da bude manja-u ovom slučaju kada pronalazi √A jedinstvenih vrednosti ali ne 2√A, što dalje ograničava broj jedinstvenih vrednosti koji se nalaze u bilo kom A ili B bloku.

Označavanje A bloka se odvija √A puta za svaki A podniz, zatim se A blokovi rolaju i ubacuju u B blolove u √A puta. Lokalno spajanje takođe zahteva O(n) složenost za standardno spajanje, mada sa više zadataka pošto vrednosti moraju zamenjene umesto kopirane. Linearna pretraga za pronalaženje novog minimuma u bloku A iterira kroz √A blokova u √A vremenu. I proces preraspodele bafera je identičan vađenju bafera ali od pozadi, i zati ima istu vremensku složenost od O(n).

Posle izostavljanja svih osim najveće složenosti i smatranjem da postoji log n nivou u spoljašnjoj petlji spajanja, a to vodi do krejnje asimptotičke složenosti od O(n log n) za najgore slučajeve. Za najbolji slučaj, gde su podaci već uređeni u poretku, korak spajanja se izvodi u n/16 poređenja za prvi nivo, onda n/32, zatim n/64, n/128, itd. Ovo je dobro poznat matematički niz (red) koji se rešava u O(n) vremenu.

Memorija

Pošto bloksort nije rekurzivan i ne zahteva upotrebu dinamičke alokacije memorije, onda to dovodi do konstantnog steka i korišćenja prostora gomile. Koristi O(1) pomoćnu memoriju, koja prihvata O(logn) bitova i prati interval od A do B koji ne može biti veći od 32 ili 64 na 32-bitnim i 64-bitnim sistemima, i zato uprošćava na O(1) prostor za bilo koji niz koji se može alocirati.

Stabilnost

Iako su se elementi tokom bloksorta ispomerali, svaka operacija i prvobitno uređenje se može vratiti po završetku.

Stabilnost zahteva da prva instanca svake vrednosti niza i dalje posle sortiranja ostane prva instanca. Bloksort pomera ove prve instance na pocetak niza da bi napravio dva unutrašnja bafera, ali kada se završe sva spajanja za trenutni nivo, te vrednosti se vraćaju nazad na prve sortiranepozicije niza. Ovo omogućava stabilnosst.

Pre rolanja A blokova kroz B blokove, u svakom A bloku se zameni druga vrednost sa vrednošću prvog bafera. U tom trenutku A blokovi su gube uređenost zbog rolanja kroz B blokove. Međutim, kada se jednom nađe mesto gde treba da se ubaci najmanji A blok u prethodni B blok, najmanji A blok se vraća nazad na početak A blokova i njegova druga vrednost se obnavlja. Dok se ne ubace svi A blokovi, A blokovi će biti u poretku i prvi bafer će sadržati prvobitne vrednosti u prvobitnom poretku.

Koristimo drugi bafer za zamenu prilikom spajanja A blok sa nekim B vrednostima, i tada se sadržaj bafera preuređuje. Međutim, pošto je algoritam već osigurao da bafer samo sadrži samo jedinstvene vrednosti, dovoljno je samo sortiranje sadržaja bafera da bi povratili njihovo prvobitno stabilno stanje tj poredak.

Adaptivnost

Bloksort je adaptivno sortiranje sa dva nivou: prvi, preskače A i B podnizove koji su već u sortiranom poretku. Zatim, kada A i B treba da se spoje i podele na blokove jednakih veličina, A blokovi se samo rolaju kroz B sve dok je to neophodno, i odmah posle je svaki blok spojen sa vrednostima B. Što su više prvobitno bili uređeni podaci, toliko će manje biti B vrednosti koje treba spojiti sa A.

Prednosti

Bloksort stabilno sortiranje koje ne zahteva dodatni memorijski prostor, što je korisno u slučajevima kada se nam dovoljno slobodne memorije za alociranje O(n) bafera. Kada se koristi varijanta sa spoljašnjim baferem , može se skalirati sa O(n) memorije do znacajno manjih bafera ako je potrebno, a i dalje će algoritam raditi efikasno bez ikakvih ograničenja.

Mane

Blok sort ne koristi sortirane intervale podataka na nivou tako dobro kao neki drugi algoritmi, poput Timsort. Samo proverava za sortirane intervale na dva predefinisana nivou: A B podnizovi i A i B blokovi. Takođe teže ga je implementirati u odnosu na algoritam sortiranja spajanjem.