Tri par fusion - Merge sort

Tri par fusion

Un exemple de tri par fusion. Divisez d'abord la liste dans la plus petite unité (1 élément), puis comparez chaque élément avec la liste adjacente pour trier et fusionner les deux listes adjacentes. Enfin tous les éléments sont triés et fusionnés.
Classer	Algorithme de tri
Structure de données	Déployer
Performances dans le pire des cas	${\style d'affichage O(n\log n)}$
Le meilleur cas la performance	${\displaystyle \Omega (n\log n)}$variante typique et naturelle${\displaystyle \Omega (n)}$
Performances moyennes	${\displaystyle \Thêta (n\log n)}$
Complexité spatiale dans le pire des cas	${\style d'affichage O(n)}$total avec auxiliaire, auxiliaire avec listes chaînées${\style d'affichage O(n)}$${\style d'affichage O(1)}$

En informatique , le tri par fusion (également communément orthographié mergesort ) est un algorithme de tri efficace, généraliste et basé sur la comparaison . La plupart des implémentations produisent un tri stable , ce qui signifie que l'ordre des éléments égaux est le même en entrée et en sortie. Le tri par fusion est un algorithme de division pour régner inventé par John von Neumann en 1945. Une description et une analyse détaillées du tri par fusion ascendant sont apparues dans un rapport de Goldstine et von Neumann dès 1948.

Algorithme

Conceptuellement, un tri par fusion fonctionne comme suit :

1. Divisez la liste non triée en n sous-listes, chacune contenant un élément (une liste d'un élément est considérée comme triée).
2. Fusionnez à plusieurs reprises les sous-listes pour produire de nouvelles sous-listes triées jusqu'à ce qu'il ne reste plus qu'une seule sous-liste. Ce sera la liste triée.

Implémentation descendante

Exemple de code de type C utilisant des indices pour l'algorithme de tri par fusion descendante qui divise récursivement la liste (appelée exécutions dans cet exemple) en sous-listes jusqu'à ce que la taille de la sous-liste soit 1, puis fusionne ces sous-listes pour produire une liste triée. L'étape de recopie est évitée en alternant le sens de la fusion à chaque niveau de récursivité (sauf pour une première copie unique). Pour aider à comprendre cela, considérons un tableau avec deux éléments. Les éléments sont copiés dans B[], puis fusionnés à nouveau dans A[]. S'il y a quatre éléments, lorsque le bas du niveau de récursivité est atteint, les exécutions à élément unique de A[] sont fusionnées à B[], puis au niveau de récursivité supérieur suivant, ces exécutions à deux éléments sont fusionnées à A[ ]. Ce modèle se poursuit à chaque niveau de récursivité.

// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(B, 0, n, A);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

Le tri de l'ensemble du tableau est effectué par TopDownMergeSort(A, B, length(A)) .

Implémentation ascendante

Exemple de code de type C utilisant des indices pour l'algorithme de tri par fusion ascendant qui traite la liste comme un tableau de n sous-listes (appelées exécutions dans cet exemple) de taille 1, et fusionne de manière itérative les sous-listes entre deux tampons :

// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    // Each 1-element run in A is already "sorted".
    // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted.
    for (width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if (i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // Now work array B is full of runs of length 2*width.
        // Copy array B to array A for the next iteration.
        // A more efficient implementation would swap the roles of A and B.
        CopyArray(B, A, n);
        // Now array A is full of runs of length 2*width.
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

Implémentation descendante à l'aide de listes

Pseudocode pour l'algorithme de tri par fusion descendante qui divise récursivement la liste d'entrée en sous-listes plus petites jusqu'à ce que les sous-listes soient triées de manière triviale, puis fusionne les sous-listes tout en remontant la chaîne d'appel.

function merge_sort(list m) is
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

Dans cet exemple, la fonction de fusion fusionne les sous-listes gauche et droite.

function merge(left, right) is
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Implémentation ascendante à l'aide de listes

Pseudocode pour l'algorithme de tri par fusion ascendant qui utilise un petit tableau de taille fixe de références à des nœuds, où array[i] est soit une référence à une liste de taille 2 ⁱ ou nil . node est une référence ou un pointeur vers un nœud. La fonction merge() serait similaire à celle montrée dans l'exemple de fusion de listes de haut en bas, elle fusionne deux listes déjà triées et gère les listes vides. Dans ce cas, merge() utiliserait node pour ses paramètres d'entrée et sa valeur de retour.

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

Tri par fusion naturel

Un tri par fusion naturel est similaire à un tri par fusion ascendant, sauf que toutes les exécutions naturelles (séquences triées) dans l'entrée sont exploitées. Des exécutions monotones et bitoniques (alternées haut/bas) peuvent être exploitées, les listes (ou de manière équivalente des bandes ou des fichiers) étant des structures de données pratiques (utilisées comme des files d'attente FIFO ou des piles LIFO ). Dans le tri par fusion ascendant, le point de départ suppose que chaque exécution est longue d'un élément. En pratique, les données d'entrée aléatoires auront de nombreuses séries courtes qui seront simplement triées. Dans le cas typique, le tri par fusion naturelle peut ne pas nécessiter autant de passes car il y a moins d'exécutions à fusionner. Dans le meilleur des cas, l'entrée est déjà triée (c'est-à-dire qu'il s'agit d'une seule exécution), de sorte que le tri de fusion naturel n'a besoin que d'un seul passage à travers les données. Dans de nombreux cas pratiques, de longs parcours naturels sont présents, et pour cette raison, le tri par fusion naturel est exploité comme le composant clé de Timsort . Exemple:

Start       :  3  4  2  1  7  5  8  9  0  6
Select runs : (3  4)(2)(1  7)(5  8  9)(0  6)
Merge       : (2  3  4)(1  5  7  8  9)(0  6)
Merge       : (1  2  3  4  5  7  8  9)(0  6)
Merge       : (0  1  2  3  4  5  6  7  8  9)

Formellement, le genre de fusion naturelle est dit Runs -optimal, où est le nombre de points en , moins un. ${\displaystyle {\mathtt {Cours}}(L)}$${\style d'affichage L}$

Les tris de sélection de remplacement de tournoi sont utilisés pour rassembler les exécutions initiales pour les algorithmes de tri externes.

Une analyse

Un algorithme de tri par fusion récursif utilisé pour trier un tableau de 7 valeurs entières. Ce sont les étapes qu'un humain suivrait pour émuler le tri par fusion (de haut en bas).

Lors du tri de n objets, le tri par fusion a une performance moyenne et dans le pire des cas de O ( n  log  n ). Si le temps d'exécution du tri par fusion pour une liste de longueur n est T ( n ), alors la relation de récurrence T ( n ) = 2 T ( n /2) + n découle de la définition de l'algorithme (appliquer l'algorithme à deux listes de la moitié de la taille de la liste d'origine, et ajoutez les n étapes prises pour fusionner les deux listes résultantes). La forme fermée découle du théorème principal pour les récurrences diviser pour régner .

Le nombre de comparaisons effectuées par tri par fusion dans le pire des cas est donné par les numéros de tri . Ces nombres sont égaux ou légèrement inférieurs à ( n  ⌈ lg  n ⌉ − 2 ^{⌈lg  n ⌉} + 1), qui est compris entre ( n  lg  n − n + 1) et ( n  lg  n + n + O(lg  n ) ). Le meilleur cas du tri par fusion prend environ la moitié du nombre d'itérations que le pire des cas.

Pour un grand n et une liste d'entrée ordonnée au hasard, le nombre attendu (moyen) de comparaisons du tri par fusion approche α · n de moins que le pire des cas, où${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

Dans le pire des cas, le tri par fusion utilise environ 39 % de comparaisons en moins que le tri rapide dans son cas moyen , et en termes de déplacements, la complexité la plus défavorable du tri par fusion est O ( n  log  n ) - la même complexité que le meilleur cas du tri par fusion .

Le tri par fusion est plus efficace que le tri rapide pour certains types de listes si les données à trier ne peuvent être consultées efficacement que de manière séquentielle, et est donc populaire dans des langages tels que Lisp , où les structures de données à accès séquentiel sont très courantes. Contrairement à certaines implémentations (efficaces) du tri rapide, le tri par fusion est un tri stable.

L'implémentation la plus courante du tri par fusion n'effectue pas le tri sur place ; par conséquent, la taille de mémoire de l'entrée doit être allouée pour que la sortie triée soit stockée (voir ci-dessous pour les variations qui ne nécessitent que n /2 espaces supplémentaires).

Variantes

Les variantes du tri par fusion visent principalement à réduire la complexité de l'espace et le coût de la copie.

Une alternative simple pour réduire la surcharge d'espace à n /2 consiste à maintenir la gauche et la droite en tant que structure combinée, à ne copier que la partie gauche de m dans l'espace temporaire et à diriger la routine de fusion pour placer la sortie fusionnée dans m . Avec cette version, il est préférable d'allouer l'espace temporaire en dehors de la routine de fusion , de sorte qu'une seule allocation soit nécessaire. La copie excessive mentionnée précédemment est également atténuée, car la dernière paire de lignes avant l' instruction de résultat de retour ( fusion de fonction dans le pseudo-code ci-dessus) devient superflue.

Un inconvénient du tri par fusion, lorsqu'il est implémenté sur des tableaux, est son exigence de mémoire de travail O ( n ) . Plusieurs variantes en place ont été suggérées :

• Katajainen et al. présentent un algorithme qui nécessite une quantité constante de mémoire de travail : suffisamment d'espace de stockage pour contenir un élément du tableau d'entrée et un espace supplémentaire pour contenir O (1) pointeurs dans le tableau d'entrée. Ils atteignent une limite temporelle O ( n log n ) avec de petites constantes, mais leur algorithme n'est pas stable.
• Plusieurs tentatives ont été faites pour produire un algorithme de fusion sur place qui peut être combiné avec un tri de fusion standard (de haut en bas ou de bas en haut) pour produire un tri de fusion sur place. Dans ce cas, la notion de "sur place" peut être assouplie pour signifier "prendre de l'espace de pile logarithmique", car le tri par fusion standard nécessite cette quantité d'espace pour sa propre utilisation de la pile. Il a été montré par Geffert et al. qu'une fusion stable sur place est possible en un temps O ( n log n ) en utilisant une quantité constante d'espace de travail, mais leur algorithme est compliqué et a des facteurs constants élevés : la fusion de tableaux de longueur n et m peut prendre 5 n + 12 m + o ( m ) se déplace. Ce facteur constant élevé et cet algorithme en place compliqué ont été rendus plus simples et plus faciles à comprendre. Bing-Chao Huang et Michael A. Langston ont présenté un algorithme de temps linéaire simple et pratique de fusion sur place pour fusionner une liste triée en utilisant une quantité fixe d'espace supplémentaire. Ils ont tous deux utilisé le travail de Kronrod et d'autres. Il se fond dans un temps linéaire et un espace supplémentaire constant. L'algorithme prend un peu plus de temps en moyenne que les algorithmes de tri par fusion standard, libres d'exploiter O(n) cellules de mémoire supplémentaires temporaires, par moins d'un facteur de deux. Bien que l'algorithme soit beaucoup plus rapide d'une manière pratique, il est également instable pour certaines listes. Mais en utilisant des concepts similaires, ils ont pu résoudre ce problème. D'autres algorithmes sur place incluent SymMerge, qui prend un temps total de O (( n + m ) log ( n + m )) et est stable. Le branchement d'un tel algorithme dans le tri par fusion augmente sa complexité jusqu'au non- linéaire , mais toujours quasi - linéaire , O ( n (log n ) ² ) .
• Une fusion linéaire et sur place moderne et stable est le tri par fusion de blocs .

Une alternative pour réduire la copie en plusieurs listes est d'associer un nouveau champ d'information à chaque clé (les éléments de m sont appelés clés). Ce champ sera utilisé pour lier les clés et toute information associée ensemble dans une liste triée (une clé et ses informations associées sont appelées un enregistrement). Ensuite, la fusion des listes triées s'effectue en modifiant les valeurs des liens ; aucun enregistrement n'a besoin d'être déplacé. Un champ qui ne contient qu'un lien sera généralement plus petit qu'un enregistrement entier, donc moins d'espace sera également utilisé. Il s'agit d'une technique de tri standard, qui ne se limite pas au tri par fusion.

Utilisation avec des lecteurs de bande

Les algorithmes de type de tri par fusion ont permis de trier de grands ensembles de données sur les premiers ordinateurs dotés de petites mémoires à accès aléatoire selon les normes modernes. Les enregistrements étaient stockés sur bande magnétique et traités sur des banques de lecteurs de bande magnétique, tels que ces IBM 729 .

Un tri par fusion externe est pratique à exécuter à l'aide de lecteurs de disque ou de bande lorsque les données à trier sont trop volumineuses pour tenir dans la mémoire . Le tri externe explique comment le tri par fusion est implémenté avec les lecteurs de disque. Un tri type de lecteur de bande utilise quatre lecteurs de bande. Toutes les E/S sont séquentielles (sauf pour les rembobinages à la fin de chaque passe). Une implémentation minimale peut se contenter de deux tampons d'enregistrement et de quelques variables de programme.

Nommant les quatre lecteurs de bande comme A, B, C, D, avec les données d'origine sur A et en utilisant seulement deux tampons d'enregistrement, l'algorithme est similaire à l'implémentation ascendante , en utilisant des paires de lecteurs de bande au lieu de matrices en mémoire. L'algorithme de base peut être décrit comme suit :

1. Fusionner les paires d'enregistrements de A ; écrire des sous-listes à deux enregistrements alternativement en C et D.
2. Fusionner les sous-listes à deux enregistrements de C et D en sous-listes à quatre enregistrements ; en les écrivant alternativement à A et B.
3. Fusionner les sous-listes de quatre enregistrements de A et B en sous-listes de huit enregistrements ; en les écrivant alternativement en C et D
4. Répétez jusqu'à ce que vous ayez une liste contenant toutes les données, triées—en log ₂ ( n ) passes.

Au lieu de commencer par de très courtes exécutions, un algorithme hybride est généralement utilisé, où la passe initiale lira de nombreux enregistrements en mémoire, effectuera un tri interne pour créer une longue exécution, puis distribuera ces longues exécutions sur l'ensemble de sortie. Le pas évite de nombreux passages précoces. Par exemple, un tri interne de 1024 enregistrements économisera neuf passages. Le tri interne est souvent important car il présente un tel avantage. En fait, il existe des techniques qui peuvent rendre les exécutions initiales plus longues que la mémoire interne disponible. L'un d'eux, le « chasse-neige » de Knuth (basé sur un min-heap binaire ), génère des exécutions deux fois plus longues (en moyenne) que la taille de la mémoire utilisée.

Avec une certaine surcharge, l'algorithme ci-dessus peut être modifié pour utiliser trois bandes. Le temps d'exécution O ( n log n ) peut également être obtenu en utilisant deux files d'attente , ou une pile et une file d'attente, ou trois piles. Dans l'autre sens, en utilisant k > deux bandes (et O ( k ) éléments en mémoire), nous pouvons réduire le nombre d'opérations sur bande en O (log k ) fois en utilisant une fusion k/2 voies .

Un tri de fusion plus sophistiqué qui optimise l'utilisation du lecteur de bande (et de disque) est le tri de fusion polyphasé .

Optimiser le tri par fusion

Tri par fusion en mosaïque appliqué à un tableau d'entiers aléatoires. L'axe horizontal est l'indice du tableau et l'axe vertical est l'entier.

Sur les ordinateurs modernes, la localité de référence peut être d'une importance primordiale dans l' optimisation logicielle , car des hiérarchies de mémoire à plusieurs niveaux sont utilisées. Des versions compatibles avec le cache de l'algorithme de tri par fusion, dont les opérations ont été spécifiquement choisies pour minimiser le mouvement des pages entrant et sortant du cache mémoire d'une machine, ont été proposées. Par exemple, le L' algorithme de tri par fusion en mosaïque arrête le partitionnement des sous-tableaux lorsque des sous-tableaux de taille S sont atteints, où S est le nombre d'éléments de données s'insérant dans le cache d'un processeur. Chacun de ces sous-tableaux est trié avec un algorithme de tri sur place tel queinsertion sort, pour décourager les échanges de mémoire, et le tri par fusion normal est ensuite effectué de manière récursive standard. Cet algorithme a démontré de meilleures performances sur les machines qui bénéficient de l'optimisation du cache. (LaMarca & Ladner 1997)

Kronrod (1969) a suggéré une version alternative du tri par fusion qui utilise un espace supplémentaire constant. Cet algorithme a ensuite été affiné. ( Katajainen, Pasanen & Teuhola 1996 )

En outre, de nombreuses applications de tri externe utilisent une forme de tri par fusion où l'entrée est divisée en un nombre plus élevé de sous-listes, idéalement en un nombre pour lequel leur fusion permet toujours à l'ensemble de pages actuellement traité de tenir dans la mémoire principale.

Tri par fusion parallèle

Le tri par fusion est bien parallélisé grâce à l'utilisation de la méthode diviser pour régner . Plusieurs variantes parallèles différentes de l'algorithme ont été développées au fil des ans. Certains algorithmes de tri par fusion parallèle sont fortement liés à l'algorithme de fusion séquentielle descendante tandis que d'autres ont une structure générale différente et utilisent la méthode de fusion K-way .

Tri par fusion avec récursivité parallèle

La procédure de tri par fusion séquentielle peut être décrite en deux phases, la phase de division et la phase de fusion. Le premier consiste en de nombreux appels récursifs qui effectuent à plusieurs reprises le même processus de division jusqu'à ce que les sous-séquences soient triées de manière triviale (contenant un ou aucun élément). Une approche intuitive est la parallélisation de ces appels récursifs. Le pseudo-code suivant décrit le tri par fusion avec récursivité parallèle à l'aide des mots-clés fork et join :

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

Cet algorithme est la modification triviale de la version séquentielle et ne se parallélise pas bien. Par conséquent, son accélération n'est pas très impressionnante. Il a une portée de , ce qui n'est qu'une amélioration de par rapport à la version séquentielle (voir Introduction aux algorithmes ). Cela est principalement dû à la méthode de fusion séquentielle, car c'est le goulot d'étranglement des exécutions parallèles. ${\displaystyle \Thêta (n)}$${\displaystyle \Thêta (\log n)}$

Tri par fusion avec fusion parallèle

Un meilleur parallélisme peut être obtenu en utilisant un algorithme de fusion parallèle . Cormen et al. présentent une variante binaire qui fusionne deux sous-séquences triées en une seule séquence de sortie triée.

Dans l'une des séquences (la plus longue si longueur inégale), l'élément de l'index du milieu est sélectionné. Sa position dans l'autre séquence est déterminée de telle sorte que cette séquence resterait triée si cet élément était inséré à cette position. Ainsi, on sait combien d'autres éléments des deux séquences sont plus petits et la position de l'élément sélectionné dans la séquence de sortie peut être calculée. Pour les séquences partielles des éléments plus petits et plus grands ainsi créées, l'algorithme de fusion est à nouveau exécuté en parallèle jusqu'à ce que le cas de base de la récursivité soit atteint.

Le pseudocode suivant montre la méthode de tri par fusion parallèle modifiée utilisant l'algorithme de fusion parallèle (adopté de Cormen et al.).

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Afin d'analyser une relation de récurrence pour le pire des cas, les appels récursifs de parallelMergesort ne doivent être incorporés qu'une seule fois en raison de leur exécution parallèle, obtenant

$${\displaystyle T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+ T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \ gauche(\log(n)^{2}\droite).}$$

Pour plus d'informations sur la complexité de la procédure de fusion parallèle, consultez Algorithme de fusion .

La solution de cette récurrence est donnée par

$${\displaystyle T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right).}$$

Cet algorithme de fusion parallèle atteint un parallélisme de , qui est bien supérieur au parallélisme de l'algorithme précédent. Un tel tri peut bien fonctionner en pratique lorsqu'il est combiné avec un tri séquentiel rapide et stable, tel que le tri par insertion , et une fusion séquentielle rapide comme cas de base pour la fusion de petits tableaux. ${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

Tri par fusion multivoies en parallèle

Il semble arbitraire de restreindre les algorithmes de tri par fusion à une méthode de fusion binaire, car il y a généralement p > 2 processeurs disponibles. Une meilleure approche peut être d'utiliser une méthode de fusion K-way , une généralisation de la fusion binaire, dans laquelle les séquences triées sont fusionnées. Cette variante de fusion est bien adaptée pour décrire un algorithme de tri sur une PRAM . ${\style d'affichage k}$

Idée basique

Le processus de mergesort multivoie parallèle sur quatre processeurs vers .${\style d'affichage t_{0}}$${\style d'affichage t_{3}}$

Étant donné une séquence d' éléments non triée , le but est de trier la séquence avec les processeurs disponibles . Ces éléments sont répartis également entre tous les processeurs et triés localement à l'aide d'un algorithme de tri séquentiel . Par conséquent, la séquence se compose de séquences triées de longueur . Pour simplifier, soit un multiple de , de sorte que pour . ${\style d'affichage n}$${\style d'affichage p}$${\style d'affichage S_{1},...,S_{p}}$${\textstyle \lceil {\frac {n}{p}}\rceil }$${\style d'affichage n}$${\style d'affichage p}$${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$${\style d'affichage i=1,...,p}$

Ces séquences seront utilisées pour effectuer une sélection multiséquence/sélection fractionnée. Pour , l'algorithme détermine les éléments séparateurs de rang global . Ensuite, les positions correspondantes de dans chaque séquence sont déterminées avec une recherche binaire et sont donc ensuite divisées en sous- séquences avec . ${\style d'affichage j=1,...,p}$${\displaystyle v_{j}}$${\textstyle k=j{\frac {n}{p}}}$${\displaystyle v_{1},...,v_{p}}$${\style d'affichage S_{i}}$${\style d'affichage S_{i}}$${\style d'affichage p}$${\style d'affichage S_{i,1},...,S_{i,p}}$${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$

De plus, les éléments de sont affectés au processeur , c'est-à-dire tous les éléments entre rang et rang , qui sont répartis sur tout . Ainsi, chaque processeur reçoit une séquence de séquences triées. Le fait que le rang des éléments séparateurs ait été choisi globalement, fournit deux propriétés importantes : D'une part, a été choisi pour que chaque processeur puisse encore opérer sur les éléments après affectation. L'algorithme est parfaitement équilibré en charge . D'un autre côté, tous les éléments du processeur sont inférieurs ou égaux à tous les éléments du processeur . Par conséquent, chaque processeur effectue la fusion p- way localement et obtient ainsi une séquence triée à partir de ses sous-séquences. En raison de la deuxième propriété, aucune autre fusion p -way-merge ne doit être effectuée, les résultats doivent uniquement être rassemblés dans l'ordre du numéro de processeur. ${\style d'affichage S_{1,i},...,S_{p,i}}$${\style d'affichage i}$${\textstyle (i-1){\frac {n}{p}}}$${\textstyle i{\frac {n}{p}}}$${\style d'affichage S_{i}}$${\style d'affichage k}$${\displaystyle v_{i}}$${\style d'affichage k}$${\textstyle n/p}$${\style d'affichage i}$${\style d'affichage i+1}$

Sélection multi-séquences

Dans sa forme la plus simple, étant donné des séquences triées réparties uniformément sur les processeurs et un rang , la tâche consiste à trouver un élément avec un rang global dans l'union des séquences. Par conséquent, cela peut être utilisé pour diviser chacune en deux parties à un indice de séparation , où la partie inférieure ne contient que des éléments plus petits que , tandis que les éléments plus grands que sont situés dans la partie supérieure. ${\style d'affichage p}$${\style d'affichage S_{1},...,S_{p}}$${\style d'affichage p}$${\style d'affichage k}$${\style d'affichage x}$${\style d'affichage k}$${\style d'affichage S_{i}}$${\style d'affichage l_{i}}$${\style d'affichage x}$${\style d'affichage x}$

L'algorithme séquentiel présenté renvoie les indices des divisions dans chaque séquence, par exemple les indices dans les séquences dont le rang global est inférieur à et . ${\style d'affichage l_{i}}$${\style d'affichage S_{i}}$${\style d'affichage S_{i}[l_{i}]}$${\style d'affichage k}$${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
	if m_1 + ... + m_p >= k then // m_1+ ... + m_p is the global rank of v
	    r := m  // vector assignment
	else
	    l := m 
	
    return l

Pour l'analyse de complexité, le modèle PRAM est choisi. Si les données sont réparties uniformément sur tout , l'exécution p-fold de la méthode binarySearch a une durée d'exécution de . La profondeur de récursivité attendue est comme dans le Quickselect ordinaire . Ainsi, le temps de fonctionnement global attendu est de . ${\style d'affichage p}$${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log( n))}$${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$

Appliqué au tri par fusion multivoies parallèle, cet algorithme doit être invoqué en parallèle de telle sorte que tous les éléments séparateurs de rang for soient trouvés simultanément. Ces éléments séparateurs peuvent ensuite être utilisés pour partitionner chaque séquence en parties, avec le même temps d'exécution total de . ${\textstyle i{\frac {n}{p}}}$${\style d'affichage i=1,..,p}$${\style d'affichage p}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$

Pseudocode

Ci-dessous, le pseudocode complet de l'algorithme de tri par fusion multivoies parallèle est donné. Nous supposons qu'il existe une barrière de synchronisation avant et après la sélection multiséquence de sorte que chaque processeur puisse déterminer correctement les éléments de division et la partition de séquence.

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences
	    
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
	
    return o

Une analyse

Tout d'abord, chaque processeur trie localement les éléments affectés à l'aide d'un algorithme de tri de complexité . Après cela, les éléments séparateurs doivent être calculés dans le temps . Enfin, chaque groupe de divisions doit être fusionné en parallèle par chaque processeur avec un temps d'exécution d' utilisation d'un algorithme de fusion séquentiel p-way . Ainsi, le temps de fonctionnement global est donné par ${\style d'affichage n/p}$${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$${\style d'affichage p}$${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

${\displaystyle {\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\ frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$.

Adaptation et application pratiques

L'algorithme de tri par fusion multivoies est très évolutif grâce à sa capacité de parallélisation élevée, qui permet l'utilisation de nombreux processeurs. Cela fait de l'algorithme un candidat viable pour trier de grandes quantités de données, telles que celles traitées dans des grappes d'ordinateurs . De plus, étant donné que dans de tels systèmes, la mémoire n'est généralement pas une ressource limitante, l'inconvénient de la complexité spatiale du tri par fusion est négligeable. Cependant, d'autres facteurs deviennent importants dans de tels systèmes, qui ne sont pas pris en compte lors de la modélisation sur une PRAM . Ici, les aspects suivants doivent être pris en compte : la hiérarchie de la mémoire , lorsque les données ne rentrent pas dans le cache des processeurs, ou la surcharge de communication liée à l'échange de données entre les processeurs, qui pourrait devenir un goulot d'étranglement lorsque les données ne sont plus accessibles via le partage Mémoire.

Sanders et al. ont présenté dans leur article un algorithme parallèle synchrone en masse pour le tri par fusion multi-niveaux, qui divise les processeurs en groupes de taille . Tous les processeurs trient d'abord localement. Contrairement au mergesort multivoie à un seul niveau, ces séquences sont ensuite partitionnées en parties et affectées aux groupes de processeurs appropriés. Ces étapes sont répétées récursivement dans ces groupes. Cela réduit la communication et évite surtout les problèmes avec de nombreux petits messages. La structure hiérarchique du réseau réel sous-jacent peut être utilisée pour définir les groupes de processeurs (par exemple racks , clusters ,...). ${\style d'affichage p}$${\style d'affichage r}$${\style d'affichage p'}$${\style d'affichage r}$

Autres variantes

Le tri par fusion a été l'un des premiers algorithmes de tri où une vitesse optimale a été atteinte, avec Richard Cole utilisant un algorithme de sous-échantillonnage intelligent pour assurer la fusion O (1). D'autres algorithmes de tri parallèle sophistiqués peuvent atteindre des limites temporelles identiques ou meilleures avec une constante inférieure. Par exemple, en 1991, David Powers a décrit un tri rapide parallélisé (et un tri de base associé ) qui peut fonctionner en temps O (log n ) sur une machine parallèle à accès aléatoire (PRAM) CRCW avec n processeurs en effectuant un partitionnement implicitement. Powers montre en outre qu'une version en pipeline du Bitonic Mergesort de Batcher au temps O ((log n ) ² ) sur un réseau de tri papillon est en pratique en fait plus rapide que ses tris O (log n ) sur une PRAM, et il fournit une discussion détaillée de la frais généraux cachés en comparaison, tri par base et parallèle.

Comparaison avec d'autres algorithmes de tri

Bien que le tri par tas ait les mêmes limites temporelles que le tri par fusion, il ne nécessite que Θ(1) espace auxiliaire au lieu du ( n ) du tri par fusion . Sur les architectures modernes typiques, les implémentations de tri rapide efficaces surpassent généralement le tri par fusion pour le tri des tableaux basés sur la RAM. D'un autre côté, le tri par fusion est un tri stable et est plus efficace pour gérer les médias séquentiels lents à accéder. Le tri par fusion est souvent le meilleur choix pour trier une liste chaînée : dans cette situation, il est relativement facile d'implémenter un tri par fusion de telle sorte qu'il ne nécessite que Θ(1) d'espace supplémentaire et la lenteur des performances d'accès aléatoire d'un list rend certains autres algorithmes (tels que quicksort) peu performants et d'autres (tels que heapsort) complètement impossibles.

Depuis Perl 5.8, le tri par fusion est son algorithme de tri par défaut (c'était le tri rapide dans les versions précédentes de Perl). En Java , les méthodes Arrays.sort() utilisent un tri par fusion ou un tri rapide ajusté en fonction des types de données et pour l'efficacité de la mise en œuvre, passez au tri par insertion lorsque moins de sept éléments de tableau sont triés. Le noyau Linux utilise le tri par fusion pour ses listes chaînées. Python utilise Timsort , un autre hybride optimisé de tri par fusion et de tri par insertion, qui est devenu l'algorithme de tri standard dans Java SE 7 (pour les tableaux de types non primitifs), sur la plate-forme Android et dans GNU Octave .

Remarques

Les références

• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction aux algorithmes (3e éd.). MIT Press et McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen, Jyrki ; Pasanen, Tomi; Teuhola, Jukka (1996). "Fusionnage sur place pratique" . Journal nordique d'informatique . 3 (1) : 27-40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064 . Archivé de l'original le 2011-08-07 . Récupéré le 04-04-2009 .. Également pratique sur place Mergesort . Aussi [3]
• Knuth, Donald (1998). "Section 5.2.4 : Tri par fusion". Tri et recherche . L'art de la programmation informatique . 3 (2e éd.). Addison-Wesley. p. 158-168. ISBN 0-201-89685-0.
• Kronrod, MA (1969). « Algorithme de commande optimal sans champ opérationnel ». Mathématiques soviétiques - Doklady . 10 : 744.
• LaMarca, A.; Ladner, RE (1997). « L'influence des caches sur les performances de tri ». Proc. 8e Anne. ACM-SIAM Symp. Sur les algorithmes discrets (SODA97) : 370-379. CiteSeerX  10.1.1.31.1153 .
• Skiena, Steven S. (2008). "4.5 : Mergesort : tri par diviser pour régner". Le manuel de conception d'algorithmes (2e éd.). Springer. p. 120-125. ISBN 978-1-84800-069-8.
• Microsystèmes du Soleil. "API de tableaux (Java SE 6)" . Récupéré le 2007-11-19 .
• Oracle Corp. "Tableaux (Java SE 10 & JDK 10)" . Récupéré le 23/07/2018 .

Liens externes

• Algorithmes de tri animés : Fusionner le tri à la Wayback Machine (archivé le 6 mars 2015) – démonstration graphique
• Structures de données ouvertes - Section 11.1.1 - Tri par fusion , Pat Morin