Knuth a laissé cela comme un exercice (Vol 3, 5.2.5). Il existe des tris de fusion en place. Ils doivent être implémentés avec précaution.
Tout d'abord, la fusion naïve en place telle que décrite aquí n'est pas la bonne solution. Elle rétrograde les performances à O(N 2 ) .
L'idée est de trier une partie du tableau tout en utilisant le reste comme zone de travail pour la fusion.
Par exemple, comme la fonction de fusion suivante.
void wmerge(Key* xs, int i, int m, int j, int n, int w) {
while (i < m && j < n)
swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
while (i < m)
swap(xs, w++, i++);
while (j < n)
swap(xs, w++, j++);
}
Il prend le tableau xs les deux sous-réseaux triés sont représentés comme des plages [i, m) y [j, n) respectivement. La zone de travail commence à partir de w . Comparé à l'algorithme de fusion standard donné dans la plupart des manuels, celui-ci échange le contenu entre le sous-réseau trié et la zone de travail. En conséquence, la zone de travail précédente contient les éléments triés fusionnés, tandis que les éléments précédents stockés dans la zone de travail sont déplacés vers les deux sous-réseaux.
Toutefois, deux contraintes doivent être satisfaites :
- La zone de travail doit se situer dans les limites du tableau. En d'autres termes, elle doit être suffisamment grande pour contenir les éléments échangés sans provoquer d'erreur hors limites.
- La zone de travail peut être superposée à l'un ou l'autre des deux tableaux triés ; toutefois, elle doit veiller à ce qu'aucun des éléments non immergés ne soit écrasé.
Avec cet algorithme de fusion défini, il est facile d'imaginer une solution qui peut trier la moitié du tableau. La question suivante est de savoir comment traiter le reste de la partie non triée stockée dans la zone de travail comme indiqué ci-dessous :
... unsorted 1/2 array ... | ... sorted 1/2 array ...
Une idée intuitive est de trier récursivement une autre moitié de la zone de travail, ainsi il n'y a que 1/4 des éléments qui n'ont pas encore été triés.
... unsorted 1/4 array ... | sorted 1/4 array B | sorted 1/2 array A ...
Le point clé à ce stade est que nous devons fusionner les éléments 1/4 triés B avec les éléments 1/2 triés A tôt ou tard.
La zone de travail restante, qui ne contient que 1/4 des éléments, est-elle assez grande pour fusionner A et B ? Malheureusement, il ne l'est pas.
Toutefois, la deuxième contrainte mentionnée ci-dessus nous donne un indice, à savoir que nous pouvons l'exploiter en disposant la zone de travail de manière à ce qu'elle chevauche l'un ou l'autre des sous-réseaux si nous pouvons garantir à la séquence de fusion que les éléments non fusionnés ne seront pas écrasés.
En fait, au lieu de trier la seconde moitié de la zone de travail, nous pouvons trier la première moitié, et placer la zone de travail entre les deux tableaux triés comme ceci :
... sorted 1/4 array B | unsorted work area | ... sorted 1/2 array A ...
Cette configuration permet d'organiser efficacement le chevauchement de la zone de travail avec le sous-réseau A. Cette idée est proposée dans [Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. ``Practical in-place mergesort''. Nordic Journal of Computing, 1996].
Il ne reste donc plus qu'à répéter l'étape ci-dessus, ce qui réduit la zone de travail de 1/2, 1/4, 1/8, Lorsque la zone de travail devient suffisamment petite (par exemple, il ne reste que deux éléments), nous pouvons passer à un tri d'insertion trivial pour terminer cet algorithme.
Voici l'implémentation en ANSI C basée sur cet article.
void imsort(Key* xs, int l, int u);
void swap(Key* xs, int i, int j) {
Key tmp = xs[i]; xs[i] = xs[j]; xs[j] = tmp;
}
/*
* sort xs[l, u), and put result to working area w.
* constraint, len(w) == u - l
*/
void wsort(Key* xs, int l, int u, int w) {
int m;
if (u - l > 1) {
m = l + (u - l) / 2;
imsort(xs, l, m);
imsort(xs, m, u);
wmerge(xs, l, m, m, u, w);
}
else
while (l < u)
swap(xs, l++, w++);
}
void imsort(Key* xs, int l, int u) {
int m, n, w;
if (u - l > 1) {
m = l + (u - l) / 2;
w = l + u - m;
wsort(xs, l, m, w); /* the last half contains sorted elements */
while (w - l > 2) {
n = w;
w = l + (n - l + 1) / 2;
wsort(xs, w, n, l); /* the first half of the previous working area contains sorted elements */
wmerge(xs, l, l + n - w, n, u, w);
}
for (n = w; n > l; --n) /*switch to insertion sort*/
for (m = n; m < u && xs[m] < xs[m-1]; ++m)
swap(xs, m, m - 1);
}
}
Où wmerge est défini précédemment.
Le code source complet peut être trouvé aquí et l'explication détaillée peut être trouvée aquí
D'ailleurs, cette version n'est pas la plus rapide des tris par fusion car elle nécessite plus d'opérations d'échange. D'après mon test, elle est plus rapide que la version standard, qui alloue des espaces supplémentaires à chaque récursion. Mais elle est plus lente que la version optimisée, qui double le tableau original à l'avance et l'utilise pour les fusions ultérieures.
0 votes
Jolie question, je me la suis posée moi-même en lisant une question d'hier : stackoverflow.com/questions/2566459/
0 votes
Juste à titre de référence, voici une belle implémentation d'un tri stable par fusion en place . Compliqué, mais pas trop mal. J'ai fini par mettre en place à la fois un triage stable par fusion en place et un tri rapide stable en place en Java. Veuillez noter que la complexité est O(n (log n)^2).
0 votes
Il existe une méthode assez simple décrite ici : xinok.wordpress.com/2014/08/17/
0 votes
Dans l'algorithme habituel de division et de fusion, si vous définissez le tableau de pointeurs comme une liste chaînée L(i) où vous avez une adresse d'entrée qui est l'adresse du premier enregistrement dans l'ordre trié, et le pointeur à cette adresse est l'adresse du deuxième enregistrement dans l'ordre trié, et ainsi de suite, vous constaterez que vous POUVEZ fusionner deux listes chaînées "en place" en O(n). Vous vous retrouvez avec un pointeur séparé comme point d'entrée de la liste chaînée et une liste chaînée de n-1 pointeurs. Je fixe la nième entrée de la liste chaînée à zéro comme indicateur de STOP, ce qui est utile pour la fusion. Vous récurrez les résultats en utilisant i=L(i)