Interaktive Demo
Blocksort-Visualisierung
Blocksort oder Block-Mergesort ist ein stabiler Mergesort, der keinen zusätzlichen Speicher braucht. Um zwei sortierte Teile A und B zu mischen, teilt er A in Blöcke, lässt sie per Blocktausch durch B rollen und legt jeden Block dort ab, wo er hingehört.
Achte auf das letzte Mischen: Die violetten A-Blöcke rollen durch die gelben B-Werte und werden nacheinander abgelegt.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element
- Teil A (Blöcke)
- Teil B
- Verschobener Block oder Werte
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Schon sortierte Teile werden mit einem einzigen Vergleich pro Mischen erkannt.
Mittlerer Fall
O(n log n)
Mischen mit √n großen Blöcken kostet O(n) pro Ebene, über log n Ebenen.
Schlechtester Fall
O(n log n)
Die Blockgrößen hängen nie von den Werten ab, jedes Mischen bleibt also O(n).
Zusätzlicher Speicher
O(1)
Nur wenige Indizes; das Original legt sogar seine Puffer im Array selbst an.
Stabil
Ja
Blöcke behalten ihre ursprüngliche Reihenfolge, und lokales Mischen überholt nie gleiche Elemente.
In-place
Ja
Alles geschieht durch Blocktausch und Rotationen innerhalb des Arrays.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort diese Seite | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Kleine Gruppen, dann mischen
Zuerst werden kleine Gruppen mit Insertion Sort sortiert. Dann werden benachbarte Teile von unten nach oben gemischt, wie bei Mergesort, aber ohne Hilfsarray.
2. Rollen und Ablegen
A wird in Blöcke zu etwa √|A| Elementen geteilt. Der nächste B-Block tauscht mit dem ersten A-Block, so rollen die A-Blöcke durch B. Sobald der kleinste A-Block zwischen die B-Werte gehört, an denen er gerade vorbeigerollt ist, wird er per Rotation dort abgelegt.
3. Hier vereinfacht
Diese Visualisierung merkt sich die Reihenfolge der A-Blöcke in einer kleinen Liste und mischt lokal immer mit Rotationen. Das Original speichert diese Reihenfolge im Array selbst, in einem Puffer aus eindeutigen Werten, und mischt mit einem zweiten Puffer schneller.
Quellen
- Diese Visualisierung folgt WikiSort von BonzaiThePenguin, das „Ratio based stable in-place merging“ von Pok-Son Kim und Arne Kutzner umsetzt, vereinfacht wie oben beschrieben.