Блоксорт

Блоксорт

Блоксорт стабилно сортирање бројева од 1 до 16. Сортирање уметањем групе од 16, избацује два унутрашња бафера, означава А блокове (сваки величине √16 = 4 ), рола А блокове кроз Б, локално их спаја, сортира други бафер, и препраспоређује бафере.
Класа	Алгоритми сортирања
Структура података	Низ
Најгора перформанца	$O(n\log n)$
Најбоља перформанца	$O(n)$
Просечна перформанца	$O(n\log n)$
Најгора просторна комплексност	$O(1)$

Блоксорт, је алгоритам сортирања који спада у групу стабилних алгоритама сортирања, и састоји се од најмање две операције спајања и од сортирања уметањем у О(nlogn) времену у месту. Назив је добио из закључка да спајање две сортиране листе, А и Б, је еквивалентно дељењу А у блокове једнаких величина, и убацивање сваког блока А у листу Б под специјалним условима, и спајање АБ пара.

Један практичан алгоритам за блоксорт су предложили Pok-Son Kim и Arne Kutzner 2008. године.

Преглед

Спољашња петља блоксорта је идентична алгоритму сортирања спајањем са имплементацијом одоздо-нагоре, где сваки ниво сортирања спаја парове поднизова, А и Б, у величинама од 1, затим 2, па 4, 8, 16, и тако даље, све док оба подниза не буду постали један низ.

Уместо спајања А и Б традиционалном методом, алгоритам спајања са блоковима дели А у одвојене блокове величина √A (што даје √A блокова), убацује се сваки блок А у Б тако да прва вредноста сваког блока А буде мања или једнака од вредности Б, локално спаја сваки блок А са било којом вредношћу између Б блока и следећег А блока. Пошто спајање и даље захтева довољно велики бафер да може да прихвати блок А који се спаја, два дела у низу су резервисана за ову сврху (познатији као интерни тј унутрашњи бафери). Прва два А блока су зато модификована да садрже прву инстанцу сваке вредности из А, са правим садржајем ових блокова који се померају (шифтују) ако је неопходно. Преостали А блок се онда умеће у Б и спаја се помућу једног од два бафера који служе као простор замене. Због овог процеса, вредност у том баферу се мора преуредити.

Једном кад се сваки А и Б блок сваког А и Б подниза споје за тај ниво сортирања спајањем, онда се вредности у том баферу могу сортирати да би повратили своје првобитно уредјење (поредак), па се сортирање уметањем мора искористити. Вредности у баферима се расподељују према њиховим првим сортираним позицијама у низу. Овај процес се понавља за сваки ниво сортирања спајањем (спољашња одоздо нагоре имплементација), и у том тренутку низ ће бити стабилно сортиран.

Алгоритам

Следећи оператори се користе у примеру кода:

|	инклузивно или
>>	шифтовање удесно
%	модуло
++ i +=	инкремент
[x, y)	распон od ≥ x и < y
|распон|	распон.крај - распон.почетак
niz[i]	елемент низа

Такође, блоксорт користи следеће операције као део алгоритма:

• Замена: мења позиције две вредности у низу.
• Блок замена: мења распон вредности у низу са вредностима у другом распону низа.
• Бинарна претрага: претпостављамо да је низ сортиран, проверава средњу вредност тренутног опсега, затим ако је вредност мања проверава доњи распон, а ако је већа проверава горњи распон. Блоксорт користи две варијанте: једна која проналази прву позицију за убацивање у сортирани низ, и другу варијанту која проналази последњу позицију.
• Линеарна претрага: тражи одређену вредност у низу проверавајући сваки елемент у поретку, све док га не нађе.
• Сортирање уметањем: за сваки елемент у низу, пролази кроз петљу од позади и тражи где треба да се убаци елемент, а затим га и стави на ту позицију.
• Ротирање низа: померање елемената низа улево или десно неким бројем размака, вредностима са крајева низа. Ротацја може бити имплементирана као окретање стабла.

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

• Највећи цео број степена 2: је селдећа вредност степена 2. 63 постаје 32, 64 остаје 64, итд.

   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)

Спољашња петља

Као што смо навели, спољашња петља Блоксорта је идентична као имплементација одоздо-нагоре сортирања спајањем.

   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))

Фиксирани број цифара се такође може користити, приказивањем фактор скалирања као разломак:

   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++

Издвајање бафера

Процес избацивања бафера у блоксорту.

Два унутрашња бафера која су неопходна за сваки ниво спајања се креирају померањем првих 2√A инстанци сваке вредности унутар једног подниза А са почетком А. Алгоритам прво итерира кроз елементе у А и пребројава јединствене вредности које му требају, затим ротира низ да би померио ове јединствене вредности на поцетак. Ако А није садржао довољно јединствених вредности да попуни два бафера (исте величине √A ), Б може исто тако добро да се користи. У овом случају помера се последња инстанца сваке вредности до краја Б, са преосталим Б делом који није био укључен током спајања.

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

Ако Б не садржи довољно јединствених вредности, избацује се број са највећом јединственом вредношћу која је могла да се пронађе, затим подеси величину А и Б блока тако да број резултујућих А блокова је мањи или једнак броју избачених елемената (убачених на бафер). Само ће се један бафер користити у овом случају – други бафер неће ни постојати.

   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]

Означавање блокова

Означавање А блокова помоћу вредности из првог унутрашњег бафера. Приметите да су први А блок и последњи Б блок различитих величина.

Једном када се један или два унутрашња бафера направе, започиње се спајање сваког А и Б подниза за овај ниво сортирања спајањем. Да би се десило све то, сваки А и Б подниз се дели на једнаке блокове једнаких величина, које су израчунате у претходном кораку, где су први А блок и последњи Б блок били различитих величина (ако је било потребно). Затим се креце кроз петљу за сваки А блок и замени другу вредност са одговарајућом вредношћу из првог унутрашњег бафера. Ово се назива означавање блокова.

   // 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|

Роловање и избацивање

Два А блока се ролају кроз Б блокове. Једном када се први А бло избаци иза, блок А разлиците велицине се локално спаја са одговарајуцим Б вредностима.

После дефинисања и означавање А блокова , А блокови су уролани (увијени) у Б блокове заменом првог А блока са следећим Б блоком. Овај процес се понавља све док је прва вредност А блока са најмањом означеном вредношћу мања или једнака последњој вредности Б блока-која је управо замењена са А блоком.

У том тренутку, најмањи А блок (А блок са најмањом означеном вредношћу) је замењен на почетак роловања А блокова а означена вредност постаје првобитна вредност из првог бафера. Ово се назива избацивање блока иза, пошто се неће више роловати са преосталим А блоковима. Затим се А блок умеће у претходни Б блок, прво се користи бинарна претрага на Б да би се нашло индекс где је прва вредност А мања или једнака елементу тог индекса од Б, и затим на том индексу ротирамо А у Б.

   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))

Током овог корака може се применити оптимизација звана техника покретне-рупе. Када се најмањи (минимум) А блок избаци онда је неопходно га је ротирати у претходном Б блоку, после чега се његов садржај мењу у други унутрашњи бафер за локално спајање, а било би брже да се А блок замени у баферу унапред, и искористи предност да садржаји бафера не морају остати у поретку. Па уместо ротирања другог бафера (који је пре замене био А блок) у претходну Б блок позицију индекса, боље је вредности Б блока после индекс једноставно заменити са последњим елементима бафера.

У овом случају Покретну рупа се односи на садржај другог унутрашњег покретног бафера који је око низа, и понаша се као рупа у смислу да елементи не морају да одрже поредак.

Локално спајање

Када се једном А блок ротира у Б блок, онда је претходни А блок спаја са одговарајућим Б вредностима, ц користећи други бафер као помоћни за замену. Када се први А блок избаци иза то указује да је А блок различите величине на почетку, када се други А блок избаци иза то значи да је први А блок, и тако даље.

   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)

Ако не постоји други бафер, онда се мора применит операција спајања у месту, као што је верзија базирана на ротацији нпр. алгоритам, 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)

После избацивања минимума из А блока и спајања претходног А блока са одговарајућим Б вредностима, нови минимум А блока се мора наћи у блоковима који се још ролају кроз низ. Ово се обезбеђује покретањем линеарне претраге кроз ове А блокове и затим поређење означених вредности како бисмо нашли најмању вредност.

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

Преостали А блокови настављају ролање кроз низ а они се избацују у убацују тамо где они треба да буду. Овај процес се одвија све док сви А блокови не буду избачени и ротираниу претходни Б блок.

Када се једном избаци последњи преостали А блок и убаци у Б блок где одговара, онда треба да се споји са преосталим Б вредностима. Овим се завршава процес спајања за одређени пар поднизова А и Б. Међутим, онда се мора поновити процес за преостале поднизове А и Б за тренутни ниво сортирања спајањем.

Приметите да се унутрашњи бафери могу искористити за сваки скуп поднизова А и Б за овај ниво сортирања спајањем, и не мора се поново избацивати или модификовати у било ком смислу.

Прерасподела

Након што се споје низови А и Б, један од спољашњих бафера и даље преостане. Први спољашњи бафер је коришћен за ознаку А блокова, и његов садржај је и даље остао у истом поретку, док је други бафер преуредио свој поредак онда када је био коришћен за замену због спајања. Ово значи да се садржаји другог бафера морају сортирати другим алгоритмом, као што је сортирање уметањем. Затим, та два баера се морају прерасподелити назад у низ али са обрнутим процесом (обрнут процес у односу на његов настанак). Алгоритам блоксорт је готов после понављања ових корака на сваком нивоу имплементације одоздо нагоре алгоритма-сортирање спајањем.

Варијанте

Блоксорт са вађењем два унтрашња бафера, раyбијање поднизова А и Б у блокобе једнаких величина, ролање (рол) и испуштање А блокова у Б (користећи први бафер за праћење поретка А блокова), локално спајање користећи други бафер као простор за замену, сортирање другог бафера, и прерасподела оба бафера. Док се кораци не промене, ови подсистеми се могу разликовати у својој имплементацији.

Једна варијанта блоксорта нам дозвољава да користимо било коју количину додатне меморије, користећи овај спољашњи бафер за спајање подниза А или блока А са Б увек када А може да стане. У овој ситуацији алгоритам би био идентичан као алгоритам сортирања спајањем.

Добри избори за величину бафера укључују:

Величина	Белешке
(brojac + 1)/2	сортирање спајања поциње да ради пуном брзином, пошто ће се сви А поднизови уклопити
√(brojac + 1)/2 + 1	ово ће бити величина А блокова на највећем нивоу спајања, па блоксорт се може прескочити унутрашњим или спајањем у месту
512	бафер фиксиране величине, довољно велики да ради са разним спајањима на мањим нивоима сортирања спајањем.
0	ако систем не може да издвоји (алоцира) било коју додатну меморију, ипак ће радити добро.

Уместо означавања А блокова преко садржаја једног од унутрашњих бафера, може се користити индиректни покретни-имитациони-бафер.Ово је унутрашњи бафер дефинисан као s1 t s2, где су s1 i s2 исте величине као број А и Б блокова, и t садржи било коју вредност која прати s1 и једнака је последњој вредности s1 (што потврђује да ни једна вредност у s2 се не појављује у s1). Други унутрашњи бафер садржи √A јединствених вредности које се и даље користе. Првих √A вредности из s1 и 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 замени Б са блокм индекса j (где је први А блок иницијално индекса 0), s1[i] и s1[j] су замењени са s2[i] i s2[j]. Ово имитира покрете А блокова кроз Б. Јединствене вредности у другом баферу се користе да се одреди првобитан (оригиналан) поредак А блокова пошто се ролају кроз Б блокове. Када се једанпут избаце А блокови, покретни-имитациони бафер се користи да дешифрује да ли је дати блок у низу А блок или Б блок, сваки А блок се ротира у Б блоку, и други унутрашњи бафер секористи као простор за замену илокално спајање.

Друга вредност сваког А блока не мора да се обавезно значи – први, последњи или било који други елемент се може користите уместо. Међутим, а ко је означена прва вредност, онда ће се вредности читати од првог унутрашњег бафера (где су и замењене) приликом одлучивања где да се избаци најмањи А блок.

Постоји много алгоритама који се могу користити за сортирање садржаја другог унутрашњег бафера, укључујући и нестабилно сортирање као што је Квиксорт, пошто је садржај бафера загарантовано јединстевен. Сортирање уметањем је и даље препоручено.

Анализа

Блоксорт је добро дефинисана и истестирана класа алгоритама, која доступним имплементацијама. Ово омогућава његовим карактеристикама да се измере и узму у обзир.

Сложеност

Блоксорт започиње уметањем групе од 16-31 елемената у низ. Сортирање уметањем је O(n²) операција, па то доводи од O(16² * n/16) до O(31² * n/31), што је O(n) када се константне вредности занемаре. Такође мора се применити сортирање уметањем на други унутрашњи бафер после сваког завршеног нивоа спајања. Међутим, пошто је овај бафер ограничен на √A величине, O(√n²) операција такође се завршава са O(n).

Затим се мора извадити два унутрашња бафера за сваки ниво сортирања спајањем. То ради тако што итерира кроз елементе у А и Б поднизовима и повећава бројач увек када се промени вредност, и на налажењу довољно вредности да их ротира на почетак А или на крају Б. У најгорем случају ће се претражити цео низ пре проналажена √A nesusednih jedinstvenih vrednosti, što zahteva O(n) poređenja i √A ротација за √A Вредности. Ово се решава у O(n + √n * √n), или O(n).

Када ни А ни Б поднизови не садрже √A јединствене вредности да направе унутрашње бафере, операција спајања се одвија у месту где се понаваљано бинарно претражује и ротира А у Б. Међутим, познати недостатак јединствених вредности у било ком поднизу, је ограничење броја бинарних претрага и ротација које ће се десити током овог корака, што опет даје √A елемената ротираних у √A времени, ули O(n). Veličina svakog bloka je takođe podešena da bude manja-u ovom slučaju kada pronalazi √A јединствених вредности али не 2√A, што даље ограничава број јединствених вредности који се налазе у било ком А или Б блоку.

Означавање А блока се одвија √A пута за сваки А подниз, затим се А блокови ролају и убацују у Б блолове у √A пута. Локално спајање такође захтева О(n) сложеност за стандардно спајање, мада са више задатака пошто вредности морају замењене уместо копиране. Линеарна претрага за проналажење новог минимума у блоку А итерира кроз √A блокова у √A времену. И процес прерасподеле бафера је идентичан вађењу бафера али од позади, и зати има исту временску сложеност од О(n).

После изостављања свих осим највеће сложености и сматрањем да постоји log n нивоу у спољашњој петљи спајања, а то води до крејње асимптотичке сложености од O(n log n) за најгоре случајеве. Zа најбољи случај, где су подаци већ уређени у поретку, корак спајања се изводи у n/16 поређења за први ниво, онда n/32, затим n/64, n/128, итд. Ово је добро познат математички низ (ред) који се решава у О(n) времену.

Меморија

Пошто блоксорт није рекурзиван и не захтева употребу динамичке алокације меморије, онда то доводи до константног стека и коришћења простора гомиле. Користи О(1) помоћну меморију, која прихвата О(lоgn) битова и прати интервал од А до Б који не може бити већи од 32 или 64 на 32-битним и 64-битним системима, и зато упрошћава на О(1) простор за било који низ који се може алоцирати.

Стабилност

Иако су се елементи током блоксорта испомерали, свака операција и првобитно уређење се може вратити по завршетку.

Стабилност захтева да прва инстанца сваке вредности низа и даље после сортирања остане прва инстанца. Блоксорт помера ове прве инстанце на поцетак низа да би направио два унутрашња бафера, али када се заврше сва спајања за тренутни ниво, те вредности се враћају назад на прве сортиранепозиције низа. Ово омогућава стабилносст.

Пре ролања А блокова кроз Б блокове, у сваком А блоку се замени друга вредност са вредношћу првог бафера. У том тренутку А блокови су губе уређеност због ролања кроз Б блокове. Међутим, када се једном нађе место где треба да се убаци најмањи А блок у претходни Б блок, најмањи А блок се враћа назад на почетак А блокова и његова друга вредност се обнавља. Док се не убаце сви А блокови, А блокови ће бити у поретку и први бафер ће садржати првобитне вредности у првобитном поретку.

Користимо други бафер за замену приликом спајања А блок са неким Б вредностима, и тада се садржај бафера преуређује. Међутим, пошто је алгоритам већ осигурао да бафер само садржи само јединствене вредности, довољно је само сортирање садржаја бафера да би повратили њихово првобитно стабилно стање тј поредак.

Адаптивност

Блоксорт је адаптивно сортирање са два нивоу: први, прескаче А и Б поднизове који су већ у сортираном поретку. Затим, када А и Б треба да се споје и поделе на блокове једнаких величина, А блокови се само ролају кроз Б све док је то неопходно, и одмах после је сваки блок спојен са вредностима Б. Што су више првобитно били уређени подаци, толико ће мање бити Б вредности које треба спојити са А.

Предности

Блоксорт стабилно сортирање које не захтева додатни меморијски простор, што је корисно у случајевима када се нам довољно слободне меморије за алоцирање О(n) бафера. Када се користи варијанта са спољашњим баферем , може се скалирати са О(n) меморије до знацајно мањих бафера ако је потребно, а и даље ће алгоритам радити ефикасно без икаквих ограничења.

Мане

Блок сорт не користи сортиране интервале података на нивоу тако добро као неки други алгоритми, попут Тимсорт. Само проверава за сортиране интервале на два предефинисана нивоу: А Б поднизови и А и Б блокови. Такође теже га је имплементирати у односу на алгоритам сортирања спајањем.