Warum ist mergesort besser für verknüpfte Listen?

Einer der wichtigsten Quellen für die Effizienz von quicksort ist locality of reference, wo die computer-hardware ist so optimiert, dass der Zugriff auf Speicherbereiche, die Nähe der anderen neigt, schneller zu sein als der Zugriff auf Speicherbereiche verstreut memory. Die Partitionierung Schritt in quicksort in der Regel hat eine ausgezeichnete Lokalität, da es die Zugriffe aufeinander folgenden array-Elementen in der Nähe der Vorder-und der Rückseite. Als Ergebnis, quicksort neigt deutlich besser als andere algorithmen zur Sortierung wie heapsort, obwohl es oft tut, in etwa die gleiche Anzahl von vergleichen und swaps, da im Falle von heapsort-die Zugriffe sind mehr verstreut.

Darüber hinaus quicksort ist in der Regel viel schneller als andere algorithmen zur Sortierung, denn es arbeitet in-place, ohne die Erstellung einer Hilfs-arrays zu halten, vorläufige Werte. Im Vergleich zu so etwas wie merge-sort, kann dies ein großer Vorteil, denn die benötigte Zeit zu reservieren und freigeben des Hilfs-arrays kann spürbar sein. Betrieb im Ort verbessert auch quicksort die Lokalität.

Beim arbeiten mit verknüpften Listen, weder diese Vorteile unbedingt gilt. Da verlinkte Liste von Zellen sind oft verstreut im gesamten Speicher, es gibt keine Lokalität bonus Zugriff auf benachbarte verlinkte Liste von Zellen. Folglich, einer von quicksort ist der enorme performance-Vorteile gefressen. Ebenso werden die Vorteile der Arbeit im Ort nicht mehr gelten, da merge-sort mit dem verlinkten Liste Algorithmus benötigt keine zusätzlichen Hilfs-Speicherplatz.

Sagte, quicksort ist immer noch sehr schnell auf verketteten Listen. Merge-sort nur tendenziell schneller, da es mehr gleichmäßig teilt die Listen in der Hälfte und macht weniger Arbeit pro iteration um einen Seriendruck zu tun als die Partitionierung Schritt.

Hoffe, das hilft!