Le tri par fusion est l'un des algorithmes de tri les plus couramment utilisés en informatique et est également l'un des plus efficaces. Elle est basée sur le principe du « diviser pour régner », et cette technique est à la base d'algorithmes efficaces pour de nombreux problèmes différents.

Dans cet article, je vais parler du concept derrière cet algorithme et vous montrer un exemple en JavaScript.

Expliquer le concept

Un algorithme Divide and Conquer décompose récursivement un problème en problèmes plus petits jusqu'à ce qu'ils deviennent suffisamment simples pour être résolus. Les solutions aux sous-problèmes sont ensuite combinées pour donner une solution au problème d'origine.

Sur un algorithme de tri, l'idée est qu'il est plus facile de trier deux tableaux triés plutôt qu'un seul tableau non trié. Une fois que vous avez deux tableaux triés, vous pouvez les fusionner en un seul tableau en comparant leurs éléments un par un et en ajoutant d'abord le plus petit élément.

Le concept est assez facile à comprendre mais une question demeure. Comment atteignons-nous un état dans lequel nous avons deux tableaux triés ? Eh bien, nous pouvons y parvenir avec Divide and Conquer. Nous allons diviser le tableau en deux de manière récursive. Nous faisons cela jusqu'à ce que nous atteignions un point où nous comparons plusieurs paires de tableaux à un seul élément.

Vous pouvez voir ci-dessous exactement comment nous divisons le tableau de manière récursive en tableaux plus petits jusqu'à ce que nous n'ayons que des tableaux d'éléments uniques.

[1,9,3,8,6,5,7,4,2]
[1,9,3,8]              [6,5,7,4,2]
[1,9]       [3,8]       [6,5]       [7,4,2]
[1]   [9]   [3]   [8]   [6]   [5]   [7]     [4,2]
[1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]

[1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]
[1]   [9]   [3]   [8]   [6]   [5]   [7]     [2,4]
[1,9]       [3,8]       [5,6]       [2,4,7]
[1,3,8,9]              [2,4,5,6,7]
[1,2,3,4,5,6,7,8,9]

const mergeSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  return mergeArray(
    mergeSort(arr.slice(0, middle)), 
    mergeSort(arr.slice(middle))
  );
};
const mergeArray = (left, right) => {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
return [...result, ...left, ...right];
};
const unorderedArray = [1, 9, 3, 8, 6, 5, 7, 4, 2];
console.log(mergeSort(unorderedArray)); // Returns ordered array

Comme vous pouvez le voir dans le code, l'implémentation de l'algorithme Merge Sort est assez simple. Une fois que vous avez compris le concept, il est relativement facile à mettre en œuvre dans n'importe quelle langue.

Eh bien, c'est tout pour celui-ci. Laissez-moi savoir ce que vous pensez. Bon codage !

Plus de contenu sur plainenglish.io