Mergesort - Ist von Unten nach Oben schneller als Top-Down?

Habe ich nicht in der Lage gewesen zu finden, jede Diskussion, sagt eine Methode mergesort, sollte schneller sein als die anderen.

Bottom-up und top-down-merge-Arten, sowie andere Varianten, die sind schon gut untersucht worden in den 90er Jahren. Kurz gesagt, wenn Sie Messen die Kosten als die Anzahl der Vergleiche von einzelnen Tasten, die besten Kosten sind die gleichen (~ (n lg n)/2), die schlechteste Kosten von oben nach unten ist geringer als oder gleich der Schlimmste Fall von bottom-up - (aber die beiden ~ n lg n) und die durchschnittlichen Kosten der top-down ist, der niedriger als oder gleich dem durchschnittlichen Fall von bottom-up - (aber die beiden ~ n lg n), wo "lg n" ist der binäre Logarithmus. Die Unterschiede stammen aus der linearen Bedingungen. Natürlich, wenn n=2^p, die beiden Varianten sind in der Tat genau das gleiche. Dies bedeutet, dass, Vergleichs-Weise, von oben nach unten ist immer besser als bottom-up. Darüber hinaus wurde bewiesen, dass die "halbe-halbe" splitting Strategie der top-down-merge-sort ist optimal. Die Forschungsarbeiten sind von Flajolet, Golin, Panny, Prodinger, Chen, Hwang und Sedgewick.

Hier ist, was ich kam in mein Buch Design und Auswertung von Rein Funktionalen Programmen (College Publications, UK), in Erlang:

tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T)           -> T.

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S,    T,      U) -> mrg(tms(S),tms(T)).

mrg(     [],    T)            -> T;
mrg(      S,   [])            -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg(  [X|S],    T)            -> [X|mrg(S,T)].

Beachten Sie, dass dies nicht ein stabiles Sortieren. Auch in Erlang (und OCaml), die Sie verwenden müssen Aliase (ALIAS=...) in die Muster, wenn Sie möchten, um Speicherplatz zu sparen. Der trick hier ist, zu finden, die Mitte der Liste, ohne zu wissen, seine Länge. Dies geschieht durch cutr/3 übernimmt zwei Zeiger auf die input-Liste: man wird um eins inkrementiert, und die anderen zwei, so dass, wenn das zweite Ende erreicht hat, die erste ist in der Mitte. (Ich lernte dies von einem paper von Olivier Danvy.) Auf diese Weise, Sie brauchen nicht zu verfolgen, die Länge und die Sie nicht duplizieren die Zellen der zweiten Hälfte der Liste, so dass du nur noch (1/2)n lg n extra Raum, im Vergleich zu n lg n. Dies ist nicht bekannt.

Es wird oft behauptet, dass die bottom-up Variante ist vorzuziehen, für funktionale Sprachen oder verknüpften Liste (Knuth, Panny, Prodinger), aber ich glaube nicht, dass dies wahr ist.

War ich verblüfft, wie Sie durch den Mangel an Diskussion über merge-Sorten, so habe ich meine eigene Forschung, und schrieb ein großes Kapitel darüber. Ich bereite mich gerade auf eine neue edition mit mehr material auf merge sortiert.

Übrigens, es gibt auch andere Varianten: queue merge-sort und Online-merge-sort (ich Diskutiere das letztere in meinem Buch).

[EDIT: Als Maß für die Kosten ist die Anzahl der Vergleiche, gibt es keinen Unterschied zwischen der Wahl eines Arrays vs. verkettete Liste. Natürlich, wenn Sie die Umsetzung der top-down Variante mit verknüpften Listen, müssen Sie klug sein, wie Sie nicht unbedingt wissen, die Anzahl der Tasten, aber Sie müssen, um die traverse mindestens die Hälfte der Tasten, die jeweils Zeit, und reservieren, insgesamt (1/2)n lg n-Zellen (wenn Sie clever sind). Bottom-up merge-sort mit verknüpften Listen tatsächlich mehr erfordert zusätzlichen Speicher n lg n + n-Zellen. Also, auch mit verknüpften Listen, die top-down-Variante ist die beste Wahl. So weit wie die Länge des Programms geht, kann Ihre Laufleistung variieren, aber in eine funktionale Sprache, die top-down-merge-sort kann kürzer gestaltet werden als bottom-up -, wenn die Stabilität nicht erforderlich. Es gibt einige Papiere, besprechen Implementierungen Themen von merge-sort, wie in-place - (für die Sie brauchen, arrays), oder Stabilität etc. Zum Beispiel, ist Eine Sorgfältige Analyse von Mergesort-Programme, durch Katajainen und Larsson Traff (1997).]