block sort

block sort (tsz. block sorts)

1. (informatika) Block Sort (vagy Block Merge Sort) egy fejlett rendezési algoritmus, amelyet in-place merge sort hatékonyabbá tételére terveztek. Célja: kombinálni az alacsony memóriahasználatot és a jó teljesítményt.

A Block Sort egy hibrid algoritmus, amely:

• Merge Sort ötletén alapul (felosztás-összefésülés),
• blokk-alapú memóriakezelést használ a felesleges másolások minimalizálására,
• in-place módon dolgozik, tehát nem igényel extra memóriát,
• gyakran használ Insertion Sort-ot kis blokkokhoz,
• fordítókban és szabványos könyvtárakban is előfordul, például:
  • Java TimSort,
  • Python list.sort() (részben Block Merge elvű),
  • néha std::stable_sort() alternatívájaként fejlett könyvtárakban.

Jellemző	Érték
Algoritmus típusa	Összehasonlító, stabil
Időkomplexitás	${\textstyle O(n\log n)}$
Memóriahasználat	${\textstyle O(1)}$ extra (in-place)
Stabilitás	Igen
Használat	Nagy rendezések, stabilitás kell

1. Blokkosítás:
   • A tömböt rögzített méretű blokkokra bontja.
   • Tipikusan: ${\textstyle {\sqrt {n}}}$ méretű blokkok.
2. Rendezés:
   • Először minden blokk önállóan rendeződik (gyakran Insertion Sort-tal vagy Merge Sort-tal).
3. Blokk rendezés (tag-alapú):
   • A blokkokat egy vezető (tag) elemük szerint rendezi újra, hogy a blokkok már “majdnem” sorrendben legyenek.
4. In-place Merge:
   • Két rendezett blokkot lokálisan egyesít extra memória nélkül, buffer technikával (mozgó ablak, rotáció, stb.).

Eset	Idő
Legjobb	${\textstyle O(n\log n)}$
Átlagos	${\textstyle O(n\log n)}$
Legrosszabb	${\textstyle O(n\log n)}$
Térigény	${\textstyle O(1)}$ extra memória

Teljes implementáció bonyolult (in-place merge nehéz), de vázlatosan:

void blockSort(std::vector<int>& arr) {
    int n = arr.size();
    int blockSize = sqrt(n);

    // 1. blokkokra osztás és rendezés
    for (int i = 0; i < n; i += blockSize) {
        int end = std::min(i + blockSize, n);
        std::sort(arr.begin() + i, arr.begin() + end); // vagy insertion sort
    }

    // 2. blokkok tag-ek szerinti újrarendezése (vezető elemek)
    // 3. in-place merge blokkok között
    // 
}

Egy valós implementáció bonyolult és optimalizált, például grail sort vagy wiki sort formájában.

• Nem használ nagy külső memóriát.
• Megőrzi a stabilitást, tehát egyenlő elemek sorrendje nem változik.
• Robusztus teljesítmény bármilyen bemeneten.
• Használ blokk rotációs merge technikákat a memóriahasználat optimalizálására.

• Grail Sort – teljesen in-place stabil rendező algoritmus, Block Merge elven
• TimSort – Java/Python hibridje, részben block merge-öt használ
• Block Merge Sort – szakmai körökben használt stabil, hatékony implementáció

• Stabil
• In-place (nem igényel extra tömböt)
• Jó teljesítmény bármilyen bemeneten

• Nagyon bonyolult implementálni (in-place merge nem triviális)
• Lassabb lehet, mint std::sort kis adatokon
• Nehezen optimalizálható általános célra

A Block Sort vagy Block Merge Sort egy fejlett, stabil, in-place algoritmus, amely blokk-alapú feldolgozással próbálja elérni a rendezési művelet legjobb kompromisszumát: stabilitás, memóriahatékonyság, és garantált jó teljesítmény.

• block sort - Szótár.net (en-hu)
• block sort - Sztaki (en-hu)
• block sort - Merriam–Webster
• block sort - Cambridge
• block sort - WordNet
• block sort - Яндекс (en-ru)
• block sort - Google (en-hu)
• block sort - Wikidata
• block sort - Wikipédia (angol)