Sortieren in Java und Kopieren Array, noch nlogn?

Question

Ich habe einen Blick auf ein paar Implementierungen von Mergesort in Java genommen, und es scheint, wie die Aufspaltung Teil durch die Schaffung von zwei neuen Arrays üblicherweise getan wird, nach links und rechts und Kopieren der linken und rechten Teile auf diese jeweils Arrays.

Meine Frage ist: Das gibt uns noch nlogn Zeit richtig? Weil nun jede Teilung n + n Zeit hätte (n Zeit für das Aufteilen des Arrays, n Zeit für das Zusammenführen des Arrays) und es Logn Splits gibt, so haben wir 2nlogn, was immer noch nlogn ist. Ist das richtig?

Answer 1

Welche Implementierungen haben Sie betrachtet? Die vom JDK verwendeten primären Sortieralgorithmen sind DualPivotQuicksort (für primitive Arrays), TimSort und ComparableTimSort (für Object Arrays/Sammlungen) und der unverständliche Wizardy in ArraysParallelSortHelpers für gleichzeitige Sortierungen.

Alle diese Klassen bieten hochgradig abgestimmte Implementierungen von QuickSort oder MergeSort (oder in dem parallelen Fall "CilkSort", der wie ein Concurrency-freundlicher MergeSort klingt). Diese Algorithmen sind im Allgemeinen alle O (n log (n)) - es ist impossible to do better than O(n log(n)) ohne zusätzliche Einschränkungen für Ihre Eingaben.

Zur Frage, ob diese Algorithmen im Allgemeinen verbringen O (n) Zeit Kopieren Werte Hin- und Herschalten zwischen temporären Speicher, es ist sehr viel ein Fall-zu-Fall-Frage. Wo es möglich ist, werden diese Implementierungen sicherlich versuchen, die Verwendung von O (n) extra Speicher und Zeit für lineares Kopieren zu vermeiden, aber oft ist diese Arbeit nicht wirklich der Flaschenhals. Zum Beispiel verwendet CilkSort ein sekundäres "Workspace Array", um Werte in aufeinanderfolgenden Stufen hin und her zu kopieren, was das Erzwingen von Invarianten erleichtert, da die "vorherige" Stufe immer in einem zuverlässigen Zustand ist. Trotzdem versuchen die Implementierungen unnötige Array-Kopien zu vermeiden, wann immer dies möglich ist.

Auf der öffentlichen API-Ebene werden wir feststellen, dass Collections.sort() ruft .toArray(), sortiert das Array, und kopiert dann die Werte zurück in das Original List. Dies ist in ähnlicher Weise nur eine praktische Optimierung - es schneller ist, ein Array zu sortieren und zu tun, zwei lineare Kopien als mit allen Methodenaufrufen zu behandeln (und möglicherweise ineffizient List Implementierungen, wie LinkedList) die List an Ort und Stelle zu ändern.