Non sono stato in grado di trovare alcuna discussione secondo cui un metodo di mergesort dovrebbe essere più veloce dell'altro.
I tipi di unione di tipo bottom-up e top-down, così come altre varianti, sono stati ben studiati negli anni '90. In poche parole, se si misura il costo come il numero di confronti di singole chiavi, i costi migliori sono gli stessi (~ (n lg n)/2), il peggiore costo di top-down è inferiore o uguale al peggiore caso di bottom-up (ma entrambi ~ n lg n) e il costo medio di top-down è inferiore o uguale al caso medio di bottom-up (ma entrambi ~ n lg n), dove "lg n" è il logaritmo binario. Le differenze derivano dai termini lineari. Naturalmente, se n = 2^p, le due varianti sono in effetti esattamente le stesse. Ciò significa che, a livello di confronto, il top-down è sempre meglio del bottom-up. Inoltre, è stato dimostrato che la strategia di divisione "mezzo-metà" dell'ordinamento top-down merge è ottimale. I documenti di ricerca sono di Flajolet, Golin, Panny, Prodinger, Chen, Hwang e Sedgewick.
Ecco quello che mi è venuta nel mio libro Progettazione e analisi dei programmi puramente funzionale (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)].
Si noti che questo è non una sorta stabile. Inoltre, in Erlang (e in OCaml), devi usare gli alias (ALIAS = ...) negli schemi se vuoi salvare la memoria. Il trucco qui è trovare il centro della lista senza conoscerne la lunghezza. Questo viene fatto da cutr/3 che gestisce due puntatori alla lista di input: uno è incrementato di uno e l'altro di due, quindi quando il secondo raggiunge la fine, il primo è nel mezzo. (L'ho imparato da un articolo di Olivier Danvy.In questo modo, non è necessario tenere traccia della lunghezza e non si duplicano le celle della seconda metà della lista, quindi è sufficiente (1/2) n lg n spazio extra, contro n lg n . Questo non è ben noto.
Si sostiene spesso che la variante bottom-up sia preferibile per le lingue funzionali o l'elenco collegato (Knuth, Panny, Prodinger), ma non penso che sia vero.
Sono rimasto perplesso come te dalla mancanza di discussioni sulla fusione, così ho fatto le mie ricerche e ho scritto un ampio capitolo a riguardo. Attualmente sto preparando una nuova edizione con più materiale sui tipi di fusione.
A proposito, ci sono altre varianti: l'ordinamento di unire la coda e l'ordinamento di fusione in linea (discuto quest'ultimo nel mio libro).
[MODIFICA: poiché la misura del costo è il numero di confronti, non vi è alcuna differenza tra la scelta di un array rispetto a un elenco collegato. Ovviamente, se implementi la variante top-down con le liste collegate, devi essere intelligente, dato che non conosci necessariamente il numero di chiavi, ma dovrai attraversare almeno la metà delle chiavi, ogni volta, e riallocare, in totale (1/2) n lg n celle (se sei intelligente). L'ordinamento merge bottom-up con elenchi concatenati richiede in realtà più memoria extra, n lg n + n celle. Quindi, anche con le liste collegate, la variante top-down è la scelta migliore. Per quanto riguarda la durata del programma, il tuo chilometraggio può variare, ma in un linguaggio funzionale, l'ordinamento merge top-down può essere reso più breve del bottom-up, se la stabilità non è richiesta. Ci sono alcuni articoli che trattano problemi di implementazione di un tipo di unione, come in-place (per cui hai bisogno di array), stabilità ecc. Ad esempio, Un'analisi meticolosa dei programmi di Mergesort, di Katajainen e Larsson Traff (1997).]
I confronti e gli interscambi sono gli elementi di costo chiave nell'analisi di ordinamento, ne sono abbastanza sicuro. – Pointy
@Pointy yes, sarebbero normalmente gli elementi da analizzare quando si confrontano diversi algoritmi di ordinamento. Ma in questo caso, dovrebbero essere uguali ... sono lo stesso algoritmo, quindi non è quello che cerco. La mia implementazione rispecchia ciò che è nel libro ... è possibile che solo quello bottom-up utilizzi un minor numero di cicli sopra/attraverso l'array ma abbia lo stesso numero di confronti/mosse? – arthurakay
@NiklasB. Vedo il tuo punto ... ma quelli non stanno contribuendo alla disparità nel mio conteggio delle iterazioni. Se guardi il mio codice, sto solo monitorando le iterazioni all'interno dei loop ricorsivi/iterativi. Math.floor() non ha nulla a che fare con esso - Non sto usando un'analisi basata sul tempo – arthurakay