[Java] Schreiben Sie eine schnellere Sortierung als Arrays.sort

Ich mache Wettbewerbsprogrammierung mit Java, aber der schlechteste Berechnungsbetrag der Funktion Arrays.sort, die das in der Standardbibliothek von Java bereitgestellte Array vom primitiven Typ sortiert, ist $ O (N ^ 2). Ich habe gehört, dass es $ ist, und ich habe meine eigene Sortierfunktion implementiert, weil es schlecht war (wenn es jedoch nicht primitiv ist, scheint es, dass die schlechteste $ O (N \ log N) $ Merge-Sortierung verwendet wird. Stabil Dies kann sich ebenfalls ändern, da es sich garantiert nur um eine Sorte handelt.

(Ergänzung 2020/04/14 15:27) Es scheint, dass Java 14 so geändert wurde, dass der schlechteste Berechnungsbetrag $ O (N \ log N) $ wie folgt ist. Es scheint jedoch einige Zeit zu dauern, bis Java 14 in Wettbewerbsprofis verwendet werden kann, also selbst erstelltes Sortieren Sieht gut aus. [Java 14 Arrays.sort (int [])](https://docs.oracle.com/de/java/javase/14/docs/api/java.base/java/util/Arrays.html#sort #sort ( Zitiert aus int []))

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.

(Ende des Postskripts)

Außerdem wollte ich sowieso "Arrays.sort" schlagen, also implementierte ich einen Mehrmuster-Sortieralgorithmus mit einem Gerät zum Beschleunigen und verglich die Geschwindigkeit.

Dieses Mal haben wir die folgenden drei Arten von Sortieralgorithmen implementiert und gemessen, die zur Bekämpfung von "Arrays.sort" entwickelt wurden.

1. Sortierung zusammenführen (rekursive, dumme Implementierung)
2. Sortierung zusammenführen (rekursiv) + Sortierung einfügen
3. Sortierung zusammenführen (nicht rekursiv) + Sortierung einfügen
4. Radix Sort

Die für den Test verwendete Arraygröße betrug $ N = 10 ^ 5, 10 ^ 6, 10 ^ 7 $, und der Durchschnittswert mehrerer Ausführungszeiten wurde gemessen. Aufgrund der Ausführungszeit betrug $ N = 10 ^ 5 $ Wir können also nur $ 1000 $ mal messen, $ 10 ^ 6 $ für $ 100 $ mal, $ 10 ^ 7 $ für $ 10 $ mal. Die Testfälle sind java.util.Randoms nextInt () undnextLong (). Es wurde mitgeneriert, und um den Unterschied aufgrund von Eingaben zu beseitigen, wurde das generierte Array kopiert und jede Sortierung für das Array mit demselben Inhalt ausgeführt und gemessen.

Es ist bekannt, dass die Verarbeitung für sortierte Arrays als Merkmal von "Arrays.sort" explosiv ist, aber ich hielt dies für nicht wesentlich, daher wollte ich diesmal in einem zufälligen Fall gewinnen.

Sortierung zusammenführen (rekursive Version) + Sortierung einfügen

Merge Sort ist ein Algorithmus, der kurz beschreibt: Die ausführliche Erklärung wird weggelassen, da viele Leute sie bereits auf leicht verständliche Weise geschrieben haben.

Schritt 1. Teilen Sie die Sequenz in die erste und die zweite Hälfte. Schritt 2. Sortieren Sie die erste und zweite Hälfte des Arrays mit einem rekursiven Aufruf. Schritt 3. Führen Sie die sortierte erste und zweite Hälfte gut zusammen, um das Ganze zu sortieren.

Wenn Sie den allmählichen Ausdruck mit der Größe des Arrays als $ N $ formulieren, können Sie sehen, dass er zu $ O (N \ log N) $ wird. Die untere Grenze des Berechnungsumfangs für die Sortierung basierend auf dem Vergleich ist $ O. Es ist bekannt, dass es (N \ log N) $ ist, was bedeutet, dass die Bestellung schnell ausgeführt wird.

Als ich diesen Algorithmus tatsächlich schrieb und bediente, lag die Geschwindigkeit jedoch weit unter der von "Arrays.sort". Die Implementierung dieser Zusammenführungssortierung ist die später gezeigte rekursive Version von Zusammenführungssortierung +. Löschen Sie einfach den Teil "Einfügesortierung" aus dem Code "Einfügesortierung" und fügen Sie die Endbedingung hinzu. Es ist fast dieselbe, also werde ich sie weglassen.

Eine der Ursachen ist das Verhalten, wenn das Array in kleine Teile unterteilt wird. Wenn die Reihenfolge verbessert wird, werden im Allgemeinen die Berechnung und die Art und Weise, wie die Daten gespeichert werden, kompliziert, sodass der Overhead die Reihenfolge für die kleine Größe ist. Wenn es um die Zusammenführungssortierung geht, ist die geordnete minderwertige Einfügungssortierung (Einfügesortierung, rechnerische $ O (N ^ 2) $) für kleinere Größen schneller. ..

Legen Sie daher einen Grenzwert für die Arraygröße fest. Wenn ein Array mit einer Größe übergeben wird, die kleiner als der Grenzwert ist, schreiben Sie die Zusammenführungssortierung neu, um die Einfügesortierung auszuführen. Der Code mit dieser Umschreibung wird unten gezeigt. Im folgenden Code werden alle Bereiche als halboffene Abschnitte behandelt.

RecursionalMergeSort.java

//Grenzwert zum Umschalten von Zusammenführungssortierung auf Einfügesortierung
private static final int INSERTION_SORT_THRESHOLD = 60;

//Von außen sichtbare Funktionen
public static final void sort(int[] a, int from, int to) {
    sort(a, from, to, new int[a.length >> 1]);
}

// Merge Sort +Verarbeitungskörper der Einfügesortierung
//work ist ein Arbeitsbereich zum Speichern des ursprünglichen Arrays beim Zusammenführen der ersten und zweiten Hälfte..
//Arbeit wird wiederverwendet, um die Speichernutzung zu sparen.
private static final void sort(int[] a, int begin, int end, int[] work) {
    //Führen Sie eine Einfügesortierung durch, wenn die angegebene Array-Länge kleiner oder gleich dem Grenzwert ist
    if (end - begin <= INSERTION_SORT_THRESHOLD) {
        insertionSort(a, begin, end);
        return;
    }
    //Index in der Mitte des Arrays. 
    // >>1 steht für Division durch 2.
    int mid = (begin + end) >> 1;
    //Sortieren Sie die erste Hälfte des Arrays rekursiv.
    sort(a, begin, mid, work);
    //Sortieren Sie die zweite Hälfte des Arrays rekursiv.
    sort(a, mid, end, work);
    //Array-Länge der ersten Hälfte
    int len = mid - begin;
    //Kopieren Sie die erste Hälfte des Arrays in den Arbeitsbereich.
    //Das Kopieren eines Arrays ist besser als das Drehen mit einer for-Anweisung.Arraycopy arbeitet schneller
    System.arraycopy(a, begin, work, 0, len);
    //i ist der Index des Speicherziels. 
    //wi ist Arbeit(=Erste Hälfte des Arrays)Stellt dar, welchen Index Sie betrachten.
    //ti gibt an, welcher Index in der hinteren Hälfte des Arrays angezeigt wird.
    //Indizes in der zweiten Hälfte der Sequenz beginnen mit mid.
    for (int i = begin, wi = 0, ti = mid;; i++) {
        if (ti == end) {
            //Wenn Sie die ganze zweite Hälfte gesehen haben,Kopieren Sie die im Arbeitsbereich verbleibenden Elemente
            System.arraycopy(work, wi, a, i, len - wi);
            //Es müssen keine Elemente mehr zusammengeführt werden. Verlassen Sie daher die Schleife
            break;
        } else if (work[wi] > a[ti]) {
            //Vergleichen Sie das Element, das Sie in der ersten Hälfte betrachten, mit dem Element, das Sie in der zweiten Hälfte betrachten.
            //Bewahren Sie den kleineren auf,Verschieben Sie den Index zurück. 
            a[i] = a[ti++];
        } else {
            //Das gleiche wie oben.
            a[i] = work[wi++];
            //Wenn Sie mit dem Betrachten der ersten Hälfte fertig sind,Der Rest der Elemente in der zweiten Hälfte befindet sich bereits im Array
            if (wi == len) {
                break;
            }
        }
    }
}

//Einfügesortierung wird aufgerufen, wenn die Arraygröße klein ist.
private static final void insertionSort(int[] a, int from, int to) {
    //Das Array a stammt von<= x <Beim Anordnen in aufsteigender Reihenfolge im Bereich von i, 
    // a[i]Finden Sie heraus, wo Sie einfügen möchten, indem Sie das Element nach hinten verschieben.
    for (int i = from + 1; i < to; i++) {
        //Wert zum Einfügen
        int tmp = a[i];
        // a[i-1]Wenn es oben ist, besteht keine Notwendigkeit zu suchen
        if (a[i - 1] > tmp) {
            //Index des Einfügeziels
            int j = i;
            //Das erste Mal erfüllt immer die while-Bedingungsanweisung-whil
            do {
                //Bewegen Sie das Element um eins zurück.
                a[j] = a[j - 1];
                //Das Einfügeziel ist früher
                j--;
            //"Erreichen Sie den Anfang" oder "a"[i]Entdecken Sie die folgenden Elemente "
            } while (j > from && a[j - 1] > tmp);
            // a[i]Platzieren Sie es an der Stelle, an der es eingesetzt werden soll.
            a[j] = tmp;
        }
    }
}

Das Vergleichsergebnis ist wie folgt: (Einheit ist Millisekunde, unter Verwendung der gleichen Testdaten)

Es ist immer noch nicht so schnell wie "Arrays.sort", aber es ist auf eine praktisch akzeptable Geschwindigkeit beschleunigt. Unser Ziel ist es jedoch, eine schnellere Sortierung als "Arrays.sort" zu implementieren, damit es noch schneller ist.

Ein rekursiver Aufruf kann die Ursache für die Langsamkeit sein. Es wird gesagt, dass das Umschreiben des rekursiven Aufrufs in "für" oder "während" die Geschwindigkeit verbessert. Daher besteht der nächste Schritt darin, die Zusammenführungssortierung zu implementieren, die keine rekursive verwendet.

Zusammenführungssortierung (nicht rekursiv) + Einfügesortierung

In der rekursiven Version von Merge Sort wurde es mit einem Bild (= von oben nach unten) implementiert, das von oben nach unten (von größer nach kleiner) abfällt. In der nicht rekursiven Version wird es jedoch in die entgegengesetzte Richtung (= von unten nach oben) implementiert. Das heißt, zerlegen Sie zuerst das Array in kleinere Größen und sortieren Sie dann die Arrays. Nennen wir diese sortierte Unterspalte einen Block. Dann rufen wir diesen Block auf die gleiche Weise wie in der vorherigen Implementierung auf. Durch Zusammenführen von zwei zu zwei und Erhöhen der Größe wird schließlich die gesamte Spalte sortiert. Die Implementierung wird unten gezeigt, aber der Code und die Kommentare, die der rekursiven Version gemeinsam sind, werden entsprechend weggelassen.

NonRecursionalMergeSort.java

//Weil es nicht rekursiv ist,Intern generiertes Arbeitsbereichsarray(Sie müssen es nicht als Argument übergeben).
public static final void sort(int[] a, int begin, int end) {
    //Als allererstes,Führen Sie für jeden kleinen Block eine Einfügesortierung durch.
    //diesmal,Verwenden Sie den in der vorherigen Implementierung definierten Grenzwert als kleinste Blockeinheit
    //i ist der Index am Anfang des Blocks
    for (int i = begin;;) {
        //j ist der Index am Ende des Blocks(jedoch,Da es sich um einen halboffenen Abschnitt handelt, ist j nicht enthalten)
        int j = i + INSERTION_SORT_THRESHOLD;
        //Die Array-Länge ist nicht immer durch die Blockgröße teilbar.
        //Damit,Stellen Sie fest, ob der Block breit genug ist. 
        if (j < end) {//Wenn Sie genug Breite bekommen können
            //Einfügesortierung ausführen
            insertionSort(a, i, j);
        } else {//Wenn Sie nicht genug Breite haben(=Wenn Sie das Ende des Arrays erreichen)
            //Führen Sie Insertion Sort von i bis end aus.
            insertionSort(a, i, end);
            //Ich habe das Ende erreicht und bin nicht mehr auf dem Laufenden.
            break;
        }
        //Der Startpunkt des nächsten Blocks ist j. (i,Beachten Sie, dass j ein halboffener Abschnitt war)
        i = j;
    }
    //Die Länge des Bereichs der zu sortierenden Arrays.
    int len = end - begin;
    //Arbeitsbereich.Das Gleiche wie vorher,Wird verwendet, um die erste Hälfte der Sequenz zu speichern.
    //Die Grenze liegt nicht immer in der Mitte, da die Blockteilung Brüche erzeugt..
    //Deshalb,Der zu sichernde Bereich wird breiter.
    int[] work = new int[len];
    //Block ist die Größe des Blocks.Jedes Mal, wenn Sie zusammenführen, verdoppelt sich die Größe, 
    //Die Aktualisierungsformel ist blockiert<<=1.
    for (int block = INSERTION_SORT_THRESHOLD; block <= len; block <<= 1) {
        //Weil ich zwei Blöcke gleichzeitig zusammenführen werde,Berechnen Sie die Größe von zwei Blöcken.
        int twoBlocks = block << 1;
        //from ist ein Index, der auf den Anfang des ersten der beiden zusammenzuführenden Blöcke zeigt.
        //Deshalb,Fügen Sie in der Aktualisierungsformel die Größe von zwei Blöcken hinzu.
        //max ist der Maximalwert, der entnommen werden kann(-1).
        //Wenn der Bruch kleiner als ein Abschnitt ist, muss er nicht zusammengeführt werden., 
        // max = end -Die Länge eines Blocks wird als Block abgezogen.
        for (int from = begin, max = end - block; from < max; from += twoBlocks) {
            //Grenze zwischen zwei Blöcken(Zeigen Sie auf den Anfang des zweiten Blocks).
            int mid = from + block;
            //Ende des zweiten Blocks.Nehmen Sie sich min und achten Sie auf das Ende des Abschnitts.
            int to = Math.min(from + twoBlocks, end);
            //Die Zusammenführung der beiden Blöcke entspricht der rekursiven Version, daher wird die Erklärung weggelassen..
            System.arraycopy(a, from, work, 0, block);
            for (int i = from, wi = 0, ti = mid;; i++) {
                if (ti == to) {
                    System.arraycopy(work, wi, a, i, block - wi);
                    break;
                } else if (work[wi] > a[ti]) {
                    a[i] = a[ti++];
                } else {
                    a[i] = work[wi++];
                    if (wi == block) {
                        break;
                    }
                }
            }
        }
    }
}
//Die insertionSort-Methode ist mit der rekursiven Version identisch und wird daher weggelassen..

Das Vergleichsergebnis ist wie folgt.

Es scheint, dass es möglich war, erheblich zu beschleunigen, indem man es nicht rekursiv umschrieb. Es ist "Arrays.sort" überlegen.

Es gibt jedoch tatsächlich schnellere Algorithmen zum Sortieren von Arrays, deren Elemente "int" oder "long" sind.

Radix Sort

Hier implementieren wir einen Algorithmus namens Radix Sort. Der Berechnungsbetrag für Radix Sort beträgt $ O (k \ ast N), wobei die Wortlänge der koordinierenden Notation (z. B. $ 10 $ Basisnotation) $ k $ beträgt. ) $.

Radix Sort ist kein "Vergleich" -Sortieralgorithmus. Dies bedeutet, dass sich Radix Sort ohne direkten Vergleich nur auf den Wert jeder Ziffer konzentriert, wenn das Element in einer Notation dargestellt werden kann. Sie können nach sortieren. Int und long werden durch Bitspalten dargestellt, und diese Bitspalte ist nichts anderes als eine Notation. Daher werden Spalten, die aus int und long bestehen, durch Radix Sort dargestellt. Es wird sortiert. Wenn Sie sich die unten gezeigte Implementierung ansehen, sehen Sie, dass es keinen Vergleich der beiden Elemente des Arrays gibt, obwohl es sich um einen Sortieralgorithmus handelt.

Insbesondere besteht der Algorithmus aus den folgenden k Schritten, wobei k die Bitlänge ist. Durch Ausführen jedes Schritts mit $ O (N) $ wird die Summe von $ O (k \ ast N) $ Kann erreicht werden.

Schritt 1. Bereiten Sie einen Bucket vor, um das Element mit dem niedrigsten Bit 0 zu platzieren, und einen Bucket, um das Element mit dem niedrigsten Bit 1 zu platzieren, und speichern Sie die Elemente der Zahlenfolge. Schritt 2. Machen Sie dasselbe für das zweite Bit von unten wie in Schritt 1. Für zwei beliebige Elemente, die in denselben Bucket gehen, sollte die Reihenfolge, in der sie gespeichert werden, jedoch nicht die Reihenfolge der Buckets in Schritt 1 aufheben. Muss etwas sein. Schritt i. Sortieren Sie das i-te Bit von unten auf die gleiche Weise. Schritt k. Sortieren Sie das k-te Bit von unten auf die gleiche Weise.

Ich finde es schwierig, das "jedoch ..." in Schritt 2 zu verstehen, daher werde ich dem Ablauf anhand eines Beispiels folgen. Im Folgenden wird a = [010, 011, 100, 101.000] gemäß dem obigen Verfahren sortiert. Da die Wortlänge 3 beträgt, wird die Sortierung in den folgenden Schritten 1 bis 3 abgeschlossen.

Step 1. Sei a = [010, 011, 100, 101, 000] -> Bucket = [010, 100, 000], [011, 101]]. Gib dies zurück zu a und a = [010, 100, 000] , 011, 101] und aktualisiert.

Step 2. Sei a = [010, 100, 000, 011, 101] -> Bucket = [[100, 000, 101], [010, 011]]. Gib dies zurück zu a und a = [010, 100, 000] , 011, 101] und aktualisiert. Zu diesem Zeitpunkt werden [100, 000, 101], die in Bucket 0 eingegeben wurden, in derselben Reihenfolge wie vor der Verarbeitung abgelegt. Gleiches gilt für Bucket 1.

Step 3. Setzen Sie a = [100, 000, 101, 010, 011] -> Bucket = [[000, 010, 011], [100, 101]] und setzen Sie dies zurück auf a, a = [000, 010, 011 Aktualisiert mit 100, 101]. A ist sicherlich sortiert.

Das Obige ist der allgemeine Ablauf von Radix Sort, aber es gibt ein großes Problem: Es ist die Behandlung negativer Zahlen. Viele Sprachen wie "Java" verwenden die Komplementdarstellung von 2, um negative ganze Zahlen darzustellen Wenn der obige Algorithmus so angewendet wird, wie er ist, werden negative Zahlen mit dem höchstwertigen Bit von 1 als größer als positive Zahlen sortiert (mit anderen Worten, die Sortierung wird durchgeführt, wenn sie als "ohne Vorzeichen" betrachtet wird). Auch die Größenrelation negativer Zahlen in "vorzeichenbehaftet" und die Größenrelation "vorzeichenlos" sind genau umgekehrt. Beachten Sie daher, dass die richtige Sortierreihenfolge erhalten werden kann, indem Sie die folgenden Schritte ausführen.

Schritt 1. Führen Sie die Radix-Sortierung in absteigender Reihenfolge durch (als "ohne Vorzeichen"). Schritt 2. Die Zahlen werden in absteigender Reihenfolge nach "vorzeichenlos" sortiert, sodass die negative Zahl vor und die positive Zahl nachher gesetzt wird. Wenn Sie die Größenbeziehung als "vorzeichenbehaftet" betrachten, handelt es sich um eine negative und eine positive Zahl. Die Zahlen sind in absteigender Reihenfolge angeordnet. Wenn daher nur die negative Zahlenspalte und nur die positive Zahlenspalte invertiert werden, kann die sortierte Spalte mit "Vorzeichen" erhalten werden.

Jetzt können Sie eine Radix-Sortierung schreiben, die auch negative Zahlen unterstützt. In der unten gezeigten Implementierung werden jedoch 8 Bits als eine Stelle zusammengefasst, um die Wortlänge zu verkürzen. Mit anderen Worten, wir führen die Radix-Sortierung mit der Dezimalschreibweise $ 2 ^ 8 = 256 $ durch.

RadixSort.java

//Schaufelgröße.
private static final int BUCKET_SIZE = 256;
//weil int 32bit ist,Die Wortlänge in 256 Basen beträgt 32/ 8 = 4.
private static final int INT_RECURSION = 4;
//Senken Sie 8 Bits(Einstellige Zahl in 256 Basis)Maske zum Extrahieren
private static final int MASK = 0xff;

//Von außen sichtbare Funktionen
public static final void sort(int[] a, int from, int to) {
    sort(a, from, to, 0, new int[to - from]);
}

//Der Bucket wird durch ein eindimensionales Array dargestellt, um Speicherplatz zu sparen.
//l bedeutet, dass es jetzt Schritt l ist. (jedoch, 0-indiziert l= 0, 1, 2, 3) 
private static final void sort(int[] a, final int from, final int to, final int l, final int[] bucket) {
    //Da die Maske nach dem Verschieben nach rechts fertig ist,Berechnen Sie den richtigen Schichtbetrag.
    final int shift = l << 3;
    //Verwalten Sie die Anzahl der Elemente in jedem Eimer.
    //Ich möchte den Startpunkt jedes Buckets, also habe ich ihn als kumulative Summe.
    final int[] cnt = new int[BUCKET_SIZE + 1];
    //Verwalten Sie, wie viele in jedem Eimer platziert sind.
    final int[] put = new int[BUCKET_SIZE];
    for (int i = from; i < to; i++) {
        // a[i] >>>Bewegen Sie die gewünschten 8 Bits mit Shift auf die niedrigste Ebene.
        // (a[i] >>> shift) &MASKE sagt Ihnen, welchen Eimer Sie eingeben müssen.
        //jedoch,Da es später akkumuliert wird, verschieben Sie den Index um eins.
        cnt[((a[i] >>> shift) & MASK) + 1]++;
    }
    //Wenn Sie die Ansammlung nehmen, cnt[i]Speichert den Startpunkt des i-ten Buckets.
    for (int i = 0; i < BUCKET_SIZE; i++) {
        cnt[i + 1] += cnt[i];
    }
    for (int i = from; i < to; i++) {
        //Berechnen Sie auf die gleiche Weise wie zuvor, welchen Bucket Sie eingeben möchten.
        int bi = (a[i] >>> shift) & MASK;
        //Im Eimer aufbewahrt. 
        //Überschreiben Sie nicht, was Sie bereits platziert haben, put[bi]Erhöhen, ansteigen
        bucket[cnt[bi] + put[bi]++] = a[i];
    }
    //Ich möchte in absteigender Reihenfolge sortieren,Scannen Sie den Eimer in umgekehrter Reihenfolge
    //idx repräsentiert den Index der nächsten Position auf dem Array a.
    for (int i = BUCKET_SIZE - 1, idx = from; i >= 0; i--) {
        //Der Startpunkt des i-ten Eimers
        int begin = cnt[i];
        //i-te Eimergröße.Mit diesem cnt berechnet wird die kumulative Summe.
        int len = cnt[i + 1] - begin;
        //Kopieren Sie den Inhalt des Buckets zurück in das ursprüngliche Array.
        System.arraycopy(bucket, begin, a, idx, len);
        //Der nächste Ort zum Speichern ist len voraus
        idx += len;
    }
    //Der nächste Schritt ist Schritt l+ 1.
    final int nxtL = l + 1;
    //Gibt es noch einen Platz?
    if (nxtL < INT_RECURSION) {
        //Zum nächsten Schritt.Eimer wird wiederverwendet
        sort(a, from, to, nxtL, bucket);
        // i =Wenn Sie hier mit 0 erreicht haben,Die absteigende Sortierung nach vorzeichenlos ist abgeschlossen
        if (l == 0) {
            //Zu verwendende Variablen.
            int lft, rgt;
            //Negative Zahl in der ersten Hälfte,Da es in der zweiten Hälfte eine positive Zahl gibt, suchen Sie die Grenze in zwei Hälften.
            //Finden Sie die Anzahl der negativen Zahlen. O(log N).
            lft = from - 1; rgt = to;
            while (rgt - lft > 1) {
                int mid = (lft + rgt) >> 1;
                if (a[mid] < 0) {
                    lft = mid;
                } else {
                    rgt = mid;
                }
            }
            //Die Anzahl der negativen Zahlen ist der Wert von rgt.
            final int negative = rgt;
            //Unterspalte des Arrays a[from:negative-1](GeschlossenerAbschnitt)Umkehren.
            //Negative Zahlen sind in diesem Abschnitt in absteigender Reihenfolge angeordnet.
            lft = from; rgt = negative - 1;
            while (rgt > lft) {
                int tmp = a[lft]; a[lft] = a[rgt]; a[rgt] = tmp;
                lft++; rgt--;
            }
            //Unterspalte des Arrays a[negative:to-1](GeschlossenerAbschnitt)Umkehren.
            //Positive Zahlen sind in diesem Abschnitt in absteigender Reihenfolge angeordnet.
            lft = negative; rgt = to - 1;
            while (rgt > lft) {
                int tmp = a[lft]; a[lft] = a[rgt]; a[rgt] = tmp;
                lft++; rgt--;
            }
        }
    }
}

Das Vergleichsergebnis ist wie folgt.

Es ist ein überwältigender Sieg. Eine Sache, die Sie jedoch beachten sollten, ist, dass das Sortieren des "langen" Arrays viel Zeit in Anspruch nimmt, da die Reihenfolge proportional zur Wortlänge ist. Das Ergebnis ist, dass die Leistung von Radix Sort wie unten gezeigt beeinträchtigt wird.

Trotzdem ist es bei weitem das schnellste von allen.

Zusammenfassung

Ich glaube, ich konnte die Arrays.sort brillant gewinnen. Ich habe nicht das Gefühl, von der Radix Sort getäuscht zu werden, aber ich bin sehr froh, dass ich auch die Merge Sort gewonnen habe.