STL __merge_without_buffer Algorithmus?

Question

Wo kann ich eine anständige High-Level-Beschreibung des Algorithmus in __merge_without_buffer() in dem C ++ STL verwendet werden? Ich versuche, diesen Code in der Programmiersprache D neu zu implementieren, mit einigen Verbesserungen. Ich kann nicht zu grok scheinen, was es aus nur das Lesen der STL-Quellcode auf der algorithmischen Ebene tut, weil es zu viele Low-Level-Details es verdunkeln sind. Auch ich will nicht nur blind, um den Code zu übersetzen, weil dann, wenn es nicht funktioniert würde ich nicht weiß, warum, und ich würde nicht in der Lage sein, meine Erweiterungen hinzufügen.

Answer 1

__merge_without_buffer() ist die Durchführung einer in-place merge , als Verschmelzungsschritt eines in-place merge sort. Es nimmt als Eingabe zwei Bereiche von Daten [first, middle) und [middle, last), die bereits angenommen werden sortiert werden. Die len1 und len2 Parameter sind gleich den Längen der beiden Eingangsbereiche, nämlich (middle - first) und (last - middle) sind.

Erstens, es nimmt einen Dreh -Element. Dann wird es ordnet die Daten in der Reihenfolge A1 B1 A2 B2, wo A1 ist die Menge der Elemente in [first, middle), die kleiner als die Schwenk sind, A2 die Menge der Elemente in [first, middle) größer oder gleich dem Drehpunkt, B1 ist die Menge der Elemente in [middle, last) kleiner als der Drehpunkt, und B2 ist die Menge der Elemente in [middle, last) größer oder gleich den Drehpunkt. Beachten Sie, dass die Daten, die ursprünglich in der Reihenfolge A1 A2 B1 B2 ist, so alles, was wir tun müssen, ist A2 B1 in B1 A2 einzuschalten. Dies ist mit einem Aufruf an std::rotate(), die genau das tut.

Jetzt haben wir die Elemente herausgetrennt, die weniger als die Dreh (A1 und B1) von denen, die größer oder gleich dem Drehpunkt (A2 und B2), so können wir jetzt rekursiv die beiden Teilbereiche A1 A2 verschmelzen und B1 B2.

Wie wählen wir eine Pivot? Bei der Umsetzung auf Ich sehe, wählt sie das mittlere Element aus dem größeren Teilbereich (das heißt, wenn mehr Elemente als [first, middle) [middle, last) hat, er den Median von [first, middle) wählt, andernfalls wird der Median von [middle, last) wählt). Da die Teilbereiche bereits sortiert sind, ist der Median der Wahl trivial. Dieser Schwenk Wahl stellt sicher, dass, wenn die beiden Teilbereiche rekursiv Zusammenführen jedes Teilproblem nicht mehr als 3/4 die Größe des aktuellen Problems ist, da im schlimmsten Fall mindestens 1/4 der Elemente, die größer als oder kleiner als der Schwenk .

Was ist die Laufzeit dieses? Der std::rotate() Anruf dauert O (N) Zeit, und wir machen zwei rekursive Aufrufe zu ihnen. Dies entspricht einer Laufzeit von O (N log N). Beachten Sie jedoch, dass dies nur ein Schritt in mergesort ist: Denken Sie daran, dass in mergesort Sie zunächst rekursiv beiden Hälften sortieren und dann verschmelzen. Somit ist die Rekursion für die Laufzeit von mergesort jetzt:

T(N) = 2T(N/2) + O(N log N)

Stecken Sie diesen in die Master-Satz , und Sie bekommen, dass mergesort läuft jetzt in O (N log ² N) Zeit!

Als interessanter letzten Punkt, die folgenden drei Eigenschaften eines vergleichsbasierten Sortieralgorithmus:

1. In-place
2. Stable
3. in O Runs (N log N) Zeit

Sie können in der Regel erhalten nur 2 davon auf einmal - quicksort bekommt man (1) und (3), mergesort bekommt man (2) und (3) und eine in-Place-mergesort bekommt man (1) und (2 ). Nicht-Vergleich-basierte Sorten wie Count Art können alle 3 erreichen, aber diese Art können nur sortieren bestimmte Datentypen. Es ist möglich, gibt es eine vergleichsbasierten Sortier, die alle 3 erreicht, aber wenn es, ich bin mir nicht bewusst seine Existenz, und es ist fast sicher viel komplizierter.