Algorithmes de tri expliqués avec des exemples en JavaScript, Python, Java et C++

Qu'est-ce qu'un algorithme de tri ?

Les algorithmes de tri sont un ensemble d'instructions qui prennent un tableau ou une liste en entrée et organisent les éléments dans un ordre particulier.

Les tris sont le plus souvent numériques ou alphabétiques (ou lexicographiques), et peuvent être ascendants (A-Z, 0-9) ou décroissants (Z-A, 9-0).

Pourquoi les algorithmes de tri sont importants

Puisqu’ils peuvent souvent réduire la complexité d’un problème, les algorithmes de tri sont très importants en informatique. Ces algorithmes ont des applications directes dans les algorithmes de recherche, les algorithmes de bases de données, les méthodes diviser pour régner, les algorithmes de structure de données et bien d’autres.

Compromis des algorithmes de tri

Lors du choix d’un algorithme de tri, certaines questions doivent être posées : quelle est la taille de la collection à trier ? Quelle quantité de mémoire est disponible ? La collection doit-elle s’agrandir ?

Les réponses à ces questions peuvent déterminer quel algorithme fonctionnera le mieux pour chaque situation. Certains algorithmes comme le tri par fusion peuvent nécessiter beaucoup d'espace ou de mémoire pour s'exécuter, tandis que le tri par insertion n'est pas toujours le plus rapide, mais ne nécessite pas beaucoup de ressources pour s'exécuter.

Vous devez déterminer quels sont vos besoins et tenir compte des limites de votre système avant de décider quel algorithme de tri utiliser.

Quelques algorithmes de tri courants

Certains des algorithmes de tri les plus courants sont :

• Tri de sélection
• Tri à bulles
• Tri par insertion
• Tri par fusion
• Tri rapide
• Tri en tas
• Tri par comptage
• Tri par base
• Tri par seau

Mais avant d’aborder chacun d’entre eux, apprenons-en un peu plus sur ce qui classe un algorithme de tri.

Classification d'un algorithme de tri

Les algorithmes de tri peuvent être classés en fonction des paramètres suivants :

1. Le nombre d'échanges ou d'inversions requis : il s'agit du nombre de fois que l'algorithme permute les éléments pour trier l'entrée. Le tri par sélection nécessite le nombre minimum d'échanges.
2. Le nombre de comparaisons : il s'agit du nombre de fois que l'algorithme compare les éléments pour trier l'entrée. En utilisant la notation Big-O, les exemples d'algorithmes de tri répertoriés ci-dessus nécessitent au moins des comparaisons O(nlogn) dans le meilleur des cas, et des comparaisons O(n^2) dans le pire des cas. cas pour la plupart des sorties.
3. Qu'ils utilisent ou non la récursion : Certains algorithmes de tri, tels que le tri rapide, utilisent des techniques récursives pour trier les entrées. D'autres algorithmes de tri, tels que le tri par sélection ou le tri par insertion, utilisent des techniques non récursives. Enfin, certains algorithmes de tri, tels que le tri par fusion, utilisent à la fois des techniques récursives et non récursives pour trier les entrées.
4. Qu'ils soient stables ou instables : les algorithmes de tri stables maintiennent l'ordre relatif des éléments de valeurs égales, ou clés. Les algorithmes de tri instables ne maintiennent pas l'ordre relatif des éléments avec des valeurs/clés égales.
   
   Par exemple, imaginez que vous ayez le tableau d'entrée [1, 2, 3, 2, 4] . Et pour aider à différencier les deux valeurs égales, 2, mettons-les à jour en 2a et 2b, créant ainsi le tableau d'entrée [1 , 2a, 3, 2b, 4].
   
   Les algorithmes de tri stables conserveront l'ordre 2a et 2b, ce qui signifie que le tableau de sortie sera [1, 2a, 2b, 3, 4]. Les algorithmes de tri instables ne maintiennent pas l'ordre des valeurs égales et le tableau de sortie peut être [1, 2b, 2a, 3, 4].
   
   Tri par insertion, tri par fusion et le tri des bulles est stable. Le tri par tas et le tri rapide sont instables.
5. La quantité d'espace supplémentaire requise : Certains algorithmes de tri peuvent trier une liste sans créer une toute nouvelle liste. Ceux-ci sont connus sous le nom d’algorithmes de tri sur place et nécessitent un espace supplémentaire O(1) constant pour le tri. Pendant ce temps, les algorithmes de tri déplacés créent une nouvelle liste lors du tri.
   
   Le tri par insertion et le tri rapide sont des algorithmes de tri sur place, car les éléments sont déplacés autour d'un point pivot et n'utilisent pas de tableau séparé.
   
   Le tri par fusion est un exemple d'algorithme de tri déplacé, car la taille de l'entrée doit être allouée au préalable pour stocker la sortie pendant le processus de tri, ce qui nécessite de la mémoire supplémentaire.

Tri par seau

Le tri par compartiments est un algorithme de tri par comparaison qui opère sur les éléments en les divisant en différents compartiments, puis en triant ces compartiments individuellement. Chaque compartiment est trié individuellement à l'aide d'un algorithme de tri distinct tel que le tri par insertion, ou en appliquant l'algorithme de tri par compartiment de manière récursive.

Le tri par compartiment est principalement utile lorsque l’entrée est uniformément répartie sur une plage. Par exemple, imaginez que vous disposez d’un large éventail d’entiers à virgule flottante répartis uniformément entre une limite supérieure et une limite inférieure.

Vous pouvez utiliser un autre algorithme de tri comme le tri par fusion, le tri par tas ou le tri rapide. Cependant, ces algorithmes garantissent dans le meilleur des cas une complexité temporelle de O(nlogn).

En utilisant le tri par bucket, le tri du même tableau peut être effectué en un temps O(n).

Pseudo-code pour le tri par seau :

void bucketSort(float[] a,int n)

{

    for(each floating integer 'x' in n)

    {
        insert x into bucket[n*x]; 
    }

    for(each bucket)

    {
        sort(bucket);
    }

}

Tri par comptage

L'algorithme de tri par comptage fonctionne en créant d'abord une liste des nombres ou occurrences de chaque valeur unique dans la liste. Il crée ensuite une liste finale triée basée sur la liste des décomptes.

Une chose importante à retenir est que le tri par comptage ne peut être utilisé que lorsque vous connaissez au préalable la plage de valeurs possibles dans l’entrée.

Exemple :

Say you have a list of integers from 0 to 5:
 
input = [2, 5, 3, 1, 4, 2]

First, you need to create a list of counts for each unique value in
the `input` list. Since you know the range of the `input` is from 0 to
5, you can create a list with five placeholders for the values 0 to 5,
respectively:

count = [0, 0, 0, 0, 0, 0]
  # val: 0  1  2  3  4  5

Then, you go through the `input` list and iterate the index for each value by one.

For example, the first value in the `input` list is 2, so you add one
to the value at the second index of the `count` list, which represents
the value 2:

count = [0, 0, 1, 0, 0, 0]
  # val: 0  1  2  3  4  5
       
The next value in the `input` list is 5, so you add one to the value at
the last index of the `count` list, which represents the value 5:

count = [0, 0, 1, 0, 0, 1]
  # val: 0  1  2  3  4  5

Continue until you have the total count for each value in the `input`
list:

count = [0, 1, 2, 1, 1, 1]
  # val: 0  1  2  3  4  5

Finally, since you know how many times each value in the `input` list
appears, you can easily create a sorted `output` list. Loop through
the `count` list, and for each count, add the corresponding value
(0 - 5) to the `output` array that many times.

For example, there were no 0's in the `input` list, but there was one
occurrence of the value 1, so you add that value to the `output` array
one time:

output = [1]

Then there were two occurrences of the value 2, so you add those to the
`output` list:

output = [1, 2, 2]

And so on until you have the final sorted `output` list:

output = [1, 2, 2, 3, 4, 5]

Propriétés

• Complexité spatiale : O(k)
• Performances dans le meilleur des cas : O(n+k)
• Performance moyenne des cas : O(n+k)
• Performances dans le pire des cas : O(n+k)
• Stable : Oui (k est la plage des éléments du tableau)

Implémentation en JavaScript

let numbers = [1, 4, 1, 2, 7, 5, 2];
let count = [];
let output =[];
let i = 0;
let max = Math.max(...numbers);

// initialize counter
for (i = 0; i <= max; i++) {
  count[i] = 0;
}

// initialize output array
for (i = 0; i < numbers.length; i++) {
  output[i] = 0;
}

for (i = 0; i < numbers.length; i++) {
  count[numbers[i]]++;
}

for (i = 1; i < count.length; i++) {
  count[i] += count[i-1];
}

for (i = numbers.length - 1; i >= 0; i--) { 
  output[--count[numbers[i]]] = numbers[i];
}

// output sorted array
for (i = 0; i < output.length; i++) {
  console.log(output[i]);
}

Implémentation C++

#include <iostream>

#include <vector>

void countSort(int upperBound, int lowerBound, std::vector < int > numbersToSort) // Lower and upper bounds of numbers in vector
{
  int i;
  int range = upperBound - lowerBound; // Create a range large enough to get every number between the min and max
  std::vector < int > counts(range + 1); // Initialize of counts of the size of the range
  std::fill(counts.begin(), counts.end(), 0); // Fill vector of zeros
  std::vector < int > storedNumbers(numbersToSort.size()); // Initialize of storedNumbers of the same size as the input vector
  std::fill(storedNumbers.begin(), storedNumbers.end(), 0); // Fill storedNumbers vector of zeros

  for (i = 0; i < numbersToSort.size(); i++) {
    int index = numbersToSort[i] - lowerBound; // For example, if 5 is the lower bound and numbersToSort[i] is 5, the index will be 0 and the
    counts[index] += 1; // count of 5 will be stored in counts[0]
  }

  for (i = 1; i < counts.size(); i++) {
    counts[i] += counts[i - 1];
  }

  for (i = numbersToSort.size() - 1; i >= 0; i--) { // Copy elements from numbersToSort to storedNumbers according to the count
    storedNumbers[--counts[numbersToSort[i] - lowerBound]] = numbersToSort[i];
  }

  for (i = 0; i < storedNumbers.size(); i++) {
    std::cout << storedNumbers[i];
    if (i != storedNumbers.size() - 1)
      std::cout << ", ";
  }
  std::cout << std::endl;
}

Mise en œuvre rapide

func countingSort(_ array: [Int]) {
  // Create an array to store the count of each element
  let maxElement = array.max() ?? 0
  var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
  
  for element in array {
    countArray[element] += 1
  }
  
  for i in 1 ..< countArray.count {
    countArray[i] += countArray[i-1];
  }
  
  var sortedArray = [Int](repeating: 0, count: array.count)
  
  // copy elements from array to sortedArray according to the count
  for i in (0 ..< array.count) .reversed() {
    countArray[array[i]] -= 1
    sortedArray[countArray[array[i]]] = array[i];
  }
  
  print(sortedArray)
}

Tri par insertion

Le tri par insertion est un algorithme de tri simple pour un petit nombre d'éléments.

Exemple :

Dans le tri par insertion, vous comparez l'élément key avec les éléments précédents. Si les éléments précédents sont supérieurs à l'élément key, alors vous déplacez l'élément précédent vers la position suivante.

Commencez à partir de l’index 1 jusqu’à la taille du tableau d’entrée.

Étape 1 :

      key = 3 //starting from 1st index.

      Here `key` will be compared with the previous elements.

      In this case, `key` is compared with 8. since 8 > 3, move the element 8
      to the next position and insert `key` to the previous position.

      Result: [ 3 8 5 1 4 2 ]

Étape 2 :

      key = 5 //2nd index

      8 > 5 //move 8 to 2nd index and insert 5 to the 1st index.

      Result: [ 3 5 8 1 4 2 ]

Étape 3 :

      key = 1 //3rd index

      8 > 1     => [ 3 5 1 8 4 2 ]  

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Result: [ 1 3 5 8 4 2 ]

Étape 4 :

      key = 4 //4th index

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  stop

      Result: [ 1 3 4 5 8 2 ]

Étape 5 :

      key = 2 //5th index

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> stop

      Result: [1 2 3 4 5 8]

L'algorithme présenté ci-dessous est une version légèrement optimisée pour éviter d'échanger l'élément  key à chaque itération. Ici, l'élément  key sera échangé à la fin de l'itération (étape).

    InsertionSort(arr[])
      for j = 1 to arr.length
         key = arr[j]
         i = j - 1
         while i > 0 and arr[i] > key
            arr[i+1] = arr[i]
            i = i - 1
         arr[i+1] = key

Voici une implémentation détaillée en JavaScript :

function insertion_sort(A) {
    var len = array_length(A);
    var i = 1;
    while (i < len) {
        var x = A[i];
        var j = i - 1;
        while (j >= 0 && A[j] > x) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = x;
        i = i + 1;
    }
}

Une implémentation rapide dans Swift est présentée ci-dessous :

  var array = [8, 3, 5, 1, 4, 2]

  func insertionSort(array:inout Array<Int>) -> Array<Int>{
      for j in 0..<array.count {
          let key = array[j]
          var i = j-1

          while (i > 0 && array[i] > key){
              array[i+1] = array[i]
              i = i-1
          }
          array[i+1] = key
      }
      return array
  }

L'exemple Java est présenté ci-dessous :

public int[] insertionSort(int[] arr)
      for (j = 1; j < arr.length; j++) {
         int key = arr[j]
         int i = j - 1
         while (i > 0 and arr[i] > key) {
            arr[i+1] = arr[i]
            i -= 1
         }
         arr[i+1] = key
      }
      return arr;

Et en c....

void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1;
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
} 

Propriétés:

• Complexité spatiale : O(1)
• Complexité temporelle : O(n), O(n* n), O(n* n) pour le meilleur, la moyenne et le pire des cas respectivement.
• Meilleur cas : le tableau est déjà trié
• Cas moyen : le tableau est trié de manière aléatoire
• Dans le pire des cas : le tableau est trié à l’envers.
• Tri sur place : Oui
• Stable : Oui

Tri en tas

Heapsort est un algorithme de tri efficace basé sur l'utilisation de tas max/min. Un tas est une structure de données arborescente qui satisfait la propriété du tas : pour un tas maximum, la clé de n'importe quel nœud est inférieure ou égale à la clé de son parent (s'il a un parent).

Cette propriété peut être exploitée pour accéder au maximum d'éléments dans le tas en un temps O(logn) à l'aide de la méthode maxHeapify. Nous effectuons cette opération n fois, en déplaçant à chaque fois le maximum d'éléments du tas vers le haut du tas et en l'extrayant du tas et dans un tableau trié. Ainsi, après n itérations, nous aurons une version triée du tableau d’entrée.

L'algorithme n'est pas un algorithme sur place et nécessiterait d'abord la construction d'une structure de données en tas. L'algorithme est également instable, ce qui signifie que lors de la comparaison d'objets avec la même clé, l'ordre d'origine ne serait pas conservé.

Cet algorithme s'exécute en O(nlogn) temps et O(1) espace supplémentaire [O(n) y compris l'espace requis pour stocker les données d'entrée] puisque toutes les opérations sont effectuées entièrement sur place.

La complexité temporelle du meilleur, du pire et du cas moyen de Heapsort est O (nlogn). Bien que le tri en tas ait une meilleure complexité dans le pire des cas que le tri rapide, un tri rapide bien implémenté s'exécute plus rapidement en pratique. Il s'agit d'un algorithme basé sur la comparaison, il peut donc être utilisé pour des ensembles de données non numériques dans la mesure où une certaine relation (propriété du tas) peut être définie sur les éléments.

Une implémentation en Java est la suivante :

import java.util.Arrays;
public class Heapsort {

	public static void main(String[] args) {
		//test array
		Integer[] arr = {1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1};
		String[] strarr = {"hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random"};
		arr = heapsort(arr);
		strarr = heapsort(strarr);
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(strarr));
	}
	
	//O(nlogn) TIME, O(1) SPACE, NOT STABLE
	public static <E extends Comparable<E>> E[] heapsort(E[] arr){
		int heaplength = arr.length;
		for(int i = arr.length/2; i>0;i--){
			arr = maxheapify(arr, i, heaplength);
		}
		
		for(int i=arr.length-1;i>=0;i--){
			E max = arr[0];
			arr[0] = arr[i];
			arr[i] = max;
			heaplength--;
			arr = maxheapify(arr, 1, heaplength);
		}
		
		return arr;
	}
	
	//Creates maxheap from array
	public static <E extends Comparable<E>> E[] maxheapify(E[] arr, Integer node, Integer heaplength){
		Integer left = node*2;
		Integer right = node*2+1;
		Integer largest = node;
		
		if(left.compareTo(heaplength) <=0 && arr[left-1].compareTo(arr[node-1]) >= 0){
			largest = left;
		}
		if(right.compareTo(heaplength) <= 0 && arr[right-1].compareTo(arr[largest-1]) >= 0){
			largest = right;
		}	
		if(largest != node){
			E temp = arr[node-1];
			arr[node-1] = arr[largest-1];
			arr[largest-1] = temp;
			maxheapify(arr, largest, heaplength);
		}
		return arr;
	}
}

Implémentation en C++

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2*i + 1;  
    int r = 2*i + 2;
    if (l < n && arr[l] > arr[largest]) 
        largest = l;
    if (r < n && arr[r] > arr[largest]) 
        largest = r;
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
  
        
        heapify(arr, n, largest); 
    } 
} 
  
 
void heapSort(int arr[], int n) 
{ 
    
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>=0; i--) 
    { 

        swap(arr[0], arr[i]); 
  
        
        heapify(arr, i, 0); 
    } 
} 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    printArray(arr, n); 
}

Tri par base

Prérequis : Tri par comptage

QuickSort, MergeSort et HeapSort sont des algorithmes de tri basés sur des comparaisons. CountSort ne l’est pas. Il a la complexité de O(n+k), où k est l'élément maximum du tableau d'entrée. Ainsi, si k est O(n), CountSort devient un tri linéaire, ce qui est meilleur que les algorithmes de tri basés sur des comparaisons qui ont une complexité temporelle O(nlogn).

L'idée est d'étendre l'algorithme CountSort pour obtenir une meilleure complexité temporelle lorsque k devient O(n2). Voici l'idée de Radix Sort.

L'algorithme :

Pour chaque chiffre i où i varie du chiffre le moins significatif au chiffre le plus significatif d'un nombre, triez le tableau d'entrée à l'aide de l'algorithme de tri en fonction du ième chiffre. Nous avons utilisé le tri par nombre car il s’agit d’un tri stable.

Exemple : Supposons que le tableau d'entrée soit :

10, 21, 17, 34, 44, 11, 654, 123

Sur la base de l'algorithme, nous trierons le tableau d'entrée en fonction du chiffre un (chiffre le moins significatif).

0 : 10
1 : 21 11
2 :
3 : 123
4 : 34 44 654
5 :
6 :
7 : 17
8 :
9 :

Ainsi, le tableau devient 10, 21, 11, 123, 24, 44, 654, 17.

Maintenant, nous allons trier selon le chiffre des dizaines :

0 :
1 : 10 11 17
2 : 21 123
3 : 34
4 : 44
5 : 654
6 :
7 :
8 :
9 :

Maintenant, le tableau devient : 10, 11, 17, 21, 123, 34, 44, 654.

Enfin, on trie selon le chiffre des centaines (chiffre le plus significatif) :

0 : 010 011 017 021 034 044
1 : 123
2 :
3 :
4 :
5 :
6 : 654
7 :
8 :
9 :

Le tableau devient : 10, 11, 17, 21, 34, 44, 123, 654 qui est trié. C'est ainsi que fonctionne notre algorithme.

Une implémentation en C :

void countsort(int arr[],int n,int place){

        int i,freq[range]={0};         //range for integers is 10 as digits range from 0-9
        int output[n];

        for(i=0;i<n;i++)
                freq[(arr[i]/place)%range]++;

        for(i=1;i<range;i++)
                freq[i]+=freq[i-1];
        
        for(i=n-1;i>=0;i--){
                output[freq[(arr[i]/place)%range]-1]=arr[i];
                freq[(arr[i]/place)%range]--;
        }
        
        for(i=0;i<n;i++)
                arr[i]=output[i];
}

void radixsort(ll arr[],int n,int maxx){            //maxx is the maximum element in the array

        int mul=1;
        while(maxx){
                countsort(arr,n,mul);
                mul*=10;
                maxx/=10;
        }
}

Tri de sélection

Le tri par sélection est l'un des algorithmes de tri les plus simples. Cet algorithme tire son nom de la façon dont il parcourt le tableau : il sélectionne le plus petit élément actuel et le met en place.

Voici comment cela fonctionne:

1. Recherchez le plus petit élément du tableau et échangez-le avec le premier élément.
2. Recherchez le deuxième plus petit élément et échangez-le avec le deuxième élément du tableau.
3. Trouvez le troisième plus petit élément et échangez avec le troisième élément du tableau.
4. Répétez le processus de recherche du plus petit élément suivant et placez-le dans la position correcte jusqu'à ce que l'ensemble du tableau soit trié.

Mais comment écririez-vous le code permettant de trouver l’index de la deuxième plus petite valeur d’un tableau ?

Un moyen simple consiste à remarquer que la plus petite valeur a déjà été remplacée par l'index 0, le problème se réduit donc à trouver le plus petit élément du tableau commençant à l'index 1.

Le tri par sélection prend toujours le même nombre de comparaisons clés — N(N − 1)/2.

Implémentation en C/C++

Le programme C++ suivant contient une implémentation itérative et récursive de l'algorithme Selection Sort. Les deux implémentations sont invoquées dans la fonction main().

#include <iostream>
#include <string>
using namespace std;

template<typename T, size_t n>
void print_array(T const(&arr)[n]) {
    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << ' ';
    cout << "\n";
}

int minIndex(int a[], int i, int j) {
    if (i == j)
        return i;
    int k = minIndex(a, i + 1, j);
    return (a[i] < a[k]) ? i : k;
}

void recurSelectionSort(int a[], int n, int index = 0) {
    if (index == n)
        return;
    int k = minIndex(a, index, n - 1);
    if (k != index)
        swap(a[k], a[index]);
    recurSelectionSort(a, n, index + 1);
}

void iterSelectionSort(int a[], int n) {
    for (int i = 0; i < n; i++)
    {
        int min_index = i;
        int min_element = a[i];
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < min_element)
            {
                min_element = a[j];
                min_index = j;
            }
        }
        swap(a[i], a[min_index]);
    }
}

int main() {
    int recurArr[6] = { 100,35, 500, 9, 67, 20 };
    int iterArr[5] = { 25, 0, 500, 56, 98 };

    cout << "Recursive Selection Sort"  << "\n";
    print_array(recurArr); // 100 35 500 9 67 20
    recurSelectionSort(recurArr, 6);
    print_array(recurArr); // 9 20 35 67 100 500

    cout << "Iterative Selection Sort" << "\n";
    print_array(iterArr); // 25 0 500 56 98
    iterSelectionSort(iterArr, 5);
    print_array(iterArr); // 0 25 56 98 500
}

Implémentation en JavaScript

function selection_sort(A) {
    var len = A.length;
    for (var i = 0; i < len - 1; i = i + 1) {
        var j_min = i;
        for (var j = i + 1; j < len; j = j + 1) {
            if (A[j] < A[j_min]) {
                j_min = j;
            } else {}
        }
        if (j_min !== i) {
            swap(A, i, j_min);
        } else {}
    }
}

function swap(A, x, y) {
    var temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

Implémentation en Python

def seletion_sort(arr):
         if not arr:
         return arr
    for i in range(len(arr)):
         min_i = i
         for j in range(i + 1, len(arr)):
              if arr[j] < arr[min_i]:
                  min_i = j
         arr[i], arr[min_i] = arr[min_i], arr[i]

Implémentation en Java

public void selectionsort(int array[])
{
    int n = array.length;            //method to find length of array 
    for (int i = 0; i < n-1; i++)
    {
        int index = i;
        int min = array[i];          // taking the min element as ith element of array
        for (int j = i+1; j < n; j++)
        {
            if (array[j] < array[index])
            {
                index = j;
                min = array[j];
            }
        }
        int t = array[index];         //Interchange the places of the elements
        array[index] = array[i];
        array[i] = t;
    }
}

Implémentation dans MATLAB

function [sorted] = selectionSort(unsorted)
    len = length(unsorted);
    for i = 1:1:len
        minInd = i;
        for j = i+1:1:len
           if unsorted(j) < unsorted(minInd) 
               minInd = j;
           end
        end
        unsorted([i minInd]) = unsorted([minInd i]);    
    end
    sorted = unsorted;
end

Propriétés

• Complexité spatiale :  O(n)
• Complexité temporelle :  O(n2)
• Tri sur place : Oui
• Stable :  Non

Tri à bulles

Tout comme la façon dont les bulles montent du fond d'un verre, le tri à bulles est un algorithme simple qui trie une liste, permettant aux valeurs inférieures ou supérieures de remonter vers le haut. L'algorithme parcourt une liste et compare les valeurs adjacentes, en les échangeant si elles ne sont pas dans le bon ordre.

Avec une complexité dans le pire des cas de O(n^2), le tri à bulles est très lent par rapport à d'autres algorithmes de tri comme le tri rapide. L’avantage est qu’il s’agit de l’un des algorithmes de tri les plus faciles à comprendre et à coder à partir de zéro.

D'un point de vue technique, le tri à bulles est raisonnable pour trier des tableaux de petite taille ou spécialement lors de l'exécution d'algorithmes de tri sur des ordinateurs dotés de ressources mémoire remarquablement limitées.

Exemple :

Parcourez d’abord la liste :

• En commençant par [4, 2, 6, 3, 9], l'algorithme compare les deux premiers éléments du tableau, 4 et 2. Il les échange car 2 < 4 : [2, 4, 6, 3, 9]
• Il compare les deux valeurs suivantes, 4 et 6. Comme 4 < 6, celles-ci sont déjà dans l'ordre, et l'algorithme continue : [2, 4, 6, 3, 9]
• Les deux valeurs suivantes sont également échangées car 3 < 6 : [2, 4, 3, 6, 9]
• Les deux dernières valeurs, 6 et 9, sont déjà dans l’ordre, donc l’algorithme ne les échange pas.

Deuxième passage dans la liste :

• 2 < 4, il n'est donc pas nécessaire d'échanger les positions : [2, 4, 3, 6, 9]
• L'algorithme échange les deux valeurs suivantes car 3 < 4 : [2, 3, 4, 6, 9]
• Pas d'échange comme 4 < 6 : [2, 3, 4, 6, 9]
• Encore une fois, 6 < 9, donc aucun échange ne se produit : [2, 3, 4, 6, 9]

La liste est déjà triée, mais l'algorithme de tri à bulles ne s'en rend pas compte. Au lieu de cela, il doit effectuer un parcours complet dans la liste sans échanger de valeurs pour savoir que la liste est triée.

Troisième passage dans la liste :

• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]

Il est clair que le tri à bulles est loin d’être l’algorithme de tri le plus efficace. Pourtant, il est simple de comprendre et de mettre en œuvre vous-même.

Propriétés

• Complexité spatiale : O(1)
• Performances dans le meilleur des cas : O(n)
• Performance moyenne du cas : O(n*n)
• Performances dans le pire des cas : O(n*n)
• Stable : Oui

Explication vidéo

Algorithme de tri à bulles

Exemple en JavaScript

let arr = [1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9],
    sorted = false;

while(!sorted) {
  sorted = true;
  for(var i=0; i < arr.length; i++) {
    if(arr[i] < arr[i-1]) {
      let temp = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = temp;
      sorted = false;
    }
  }
}

Exemple en Java

public class BubbleSort {
    static void sort(int[] arr) {
        int n = arr.length;
        int temp = 0;
         for(int i=0; i < n; i++){
                 for(int x=1; x < (n-i); x++){
                          if(arr[x-1] > arr[x]){
                                 temp = arr[x-1];
                                 arr[x-1] = arr[x];
                                 arr[x] = temp;
                         }

                 }
         }

    }
    public static void main(String[] args) {

		for(int i=0; i < 15; i++){
			int arr[i] = (int)(Math.random() * 100 + 1);
		}

                System.out.println("array before sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }
                bubbleSort(arr);
                System.out.println("\n array after sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }

        }
}

Exemple en C++

// Recursive Implementation
void bubblesort(int arr[], int n)
{
	if(n==1)	//Initial Case
		return;
	bool swap_flag = false;
	for(int i=0;i<n-1;i++)	//After this pass the largest element will move to its desired location.
	{
		if(arr[i]>arr[i+1])
		{
			int temp=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=temp;
			swap_flag = true;
		}
	}
        // IF no two elements were swapped in the loop, then return, as array is sorted 
	if(swap_flag == false)
		return;
	bubblesort(arr,n-1);	//Recursion for remaining array
}

Exemple dans Swift

func bubbleSort(_ inputArray: [Int]) -> [Int] {
    guard inputArray.count > 1 else { return inputArray } // make sure our input array has more than 1 element
    var numbers = inputArray // function arguments are constant by default in Swift, so we make a copy
    for i in 0..<(numbers.count - 1) {
        for j in 0..<(numbers.count - i - 1) {
            if numbers[j] > numbers[j + 1] {
                numbers.swapAt(j, j + 1)
            }
        }
    }
    return numbers // return the sorted array
} 

Exemple en Python

def bubbleSort(arr): 
    n = len(arr) 
    for i in range(n):
        for j in range(0, n-i-1):
                if arr[j] > arr[j+1] : 
                        arr[j], arr[j+1] = arr[j+1], arr[j]
    print(arr)

Exemple en PHP

function bubble_sort($arr) {
    $size = count($arr)-1;
    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-$i; $j++) {
            $k = $j+1;
            if ($arr[$k] < $arr[$j]) {
                // Swap elements at indices: $j, $k
                list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
            }
        }
    }
    return $arr;// return the sorted array
}

$arr = array(1,3,2,8,5,7,4,0);
print("Before sorting");
print_r($arr);

$arr = bubble_sort($arr);
print("After sorting by using bubble sort");
print_r($arr);

Exemple en C

#include <stdio.h>

int BubbleSort(int array[], int n);

int main(void) {
  int arr[] = {10, 2, 3, 1, 4, 5, 8, 9, 7, 6};
  BubbleSort(arr, 10);

  for (int i = 0; i < 10; i++) {
    printf("%d", arr[i]);
  }
  return 0;
}
int BubbleSort(int array[], n)
{
for (int i = 0 ; i < n - 1; i++)
  {
    for (int j = 0 ; j < n - i - 1; j++)     //n is length of array
    {
      if (array[j] > array[j+1])      // For decreasing order use 
      {
        int swap   = array[j];
        array[j]   = array[j+1];
        array[j+1] = swap;
      }
    }
  }
}

Tri rapide

Le tri rapide est un algorithme de tri efficace « diviser pour régner ». La complexité temporelle moyenne du tri rapide est de O(nlog(n)), la complexité temporelle dans le pire des cas étant de O(n^2) en fonction de la sélection de l'élément pivot, qui divise le tableau actuel en deux sous-tableaux.

Par exemple, la complexité temporelle du tri rapide est d'environ O(nlog(n)) lorsque la sélection du pivot divise le tableau d'origine en deux sous-tableaux de taille presque égale.

D'un autre côté, si l'algorithme, qui sélectionne l'élément pivot des tableaux d'entrée, génère systématiquement 2 sous-tableaux avec une grande différence en termes de tailles de tableau, l'algorithme de tri rapide peut atteindre la complexité temporelle la plus défavorable de O (n ^2 ).

Les étapes impliquées dans le tri rapide sont :

• Choisissez un élément qui servira de pivot, dans ce cas, le dernier élément du tableau est le pivot.
• Partitionnement : triez le tableau de telle manière que tous les éléments inférieurs au pivot soient à gauche et tous les éléments supérieurs au pivot soient à droite.
• Appelez Quicksort de manière récursive, en tenant compte du pivot précédent pour subdiviser correctement les tableaux gauche et droit. (Une explication plus détaillée peut être trouvée dans les commentaires ci-dessous)

Exemples d'implémentations dans différentes langues

Implémentation en JavaScript :

const arr = [6, 2, 5, 3, 8, 7, 1, 4];

const quickSort = (arr, start, end) => {

  if(start < end) {

    // You can learn about how the pivot value is derived in the comments below
    let pivot = partition(arr, start, end);

    // Make sure to read the below comments to understand why pivot - 1 and pivot + 1 are used
    // These are the recursive calls to quickSort
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  } 

}

const partition = (arr, start, end) => { 
  let pivot = end;
  // Set i to start - 1 so that it can access the first index in the event that the value at arr[0] is greater than arr[pivot]
  // Succeeding comments will expound upon the above comment
  let i = start - 1,
      j = start;

  // Increment j up to the index preceding the pivot
  while (j < pivot) {

    // If the value is greater than the pivot increment j
    if (arr[j] > arr[pivot]) {
      j++;
    }

    // When the value at arr[j] is less than the pivot:
    // increment i (arr[i] will be a value greater than arr[pivot]) and swap the value at arr[i] and arr[j]
    else {
      i++;
      swap(arr, j, i);
      j++;
    }

  }

  //The value at arr[i + 1] will be greater than the value of arr[pivot]
  swap(arr, i + 1, pivot);

  //You return i + 1, as the values to the left of it are less than arr[i+1], and values to the right are greater than arr[i + 1]
  // As such, when the recursive quicksorts are called, the new sub arrays will not include this the previously used pivot value
  return i + 1;
}

const swap = (arr, firstIndex, secondIndex) => {
  let temp = arr[firstIndex];
  arr[firstIndex] = arr[secondIndex];
  arr[secondIndex] = temp;
}

quickSort(arr, 0, arr.length - 1);
console.log(arr);

Implémentation en C

#include<stdio.h>  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
}
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];     
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++;    
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    {
        int pi = partition(arr, low, high); 
  
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
  

void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  

int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    quickSort(arr, 0, n-1); 
    printf("Sorted array: n"); 
    printArray(arr, n); 
    return 0; 
} 

Implémentation en Python3

import random

z=[random.randint(0,100) for i in range(0,20)]

def quicksort(z):
    if(len(z)>1):        
        piv=int(len(z)/2)
        val=z[piv]
        lft=[i for i in z if i<val]
        mid=[i for i in z if i==val]
        rgt=[i for i in z if i>val]

        res=quicksort(lft)+mid+quicksort(rgt)
        return res
    else:
        return z
        
ans1=quicksort(z)
print(ans1)

Implémentation dans MATLAB

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

sorted = quicksort(a,1,length(a));

function [unsorted] =  quicksort(unsorted, low, high)
    if low < high
        [pInd, unsorted] = partition(unsorted, low, high);
        unsorted = quicksort(unsorted, low, pInd-1);
        unsorted = quicksort(unsorted, pInd+1, high);
    end

end

function [pInd, unsorted] = partition(unsorted, low, high)
    i = low-1;
    for j = low:1:high-1
        if unsorted(j) <= unsorted(high)
            i = i+1;
            unsorted([i,j]) = unsorted([j,i]);
            
        end
    end
    unsorted([i+1,high]) = unsorted([high,i+1]);
    pInd = i+1;

end

La complexité spatiale du tri rapide est O(n). Il s'agit d'une amélioration par rapport aux autres algorithmes de tri diviser pour mieux régner, qui occupent de l'espace O(nlong(n)).

Le tri rapide y parvient en modifiant l'ordre des éléments dans le tableau donné. Comparez cela avec l'algorithme de tri par fusion qui crée 2 tableaux, chaque longueur n/2, à chaque appel de fonction.

Cependant il existe le problème que cet algorithme de tri soit de temps O(n*n) si le pivot est toujours conservé au milieu. Ceci peut être surmonté en utilisant un pivot aléatoire

Complexité

Meilleur, moyen, pire, mémoire : n log(n)n log(n)n 2log(n). Ce n'est pas un algorithme stable et le tri rapide est généralement effectué sur place avec l'espace de pile O(log(n)).

La complexité spatiale du tri rapide est O(n). Il s'agit d'une amélioration par rapport aux autres algorithmes de tri diviser pour mieux régner, qui occupent un espace O(n log(n)).

Tri timbré

Timsort est un algorithme de tri rapide fonctionnant avec une complexité O(N log(N)) stable.

Timsort est un mélange de tri par insertion et de tri par fusion. Cet algorithme est implémenté dans Arrays.sort() de Java ainsi que dans sorted() et sort() de Python. Les parties plus petites sont triées à l’aide du tri par insertion et sont ensuite fusionnées à l’aide du tri par fusion.

Une implémentation rapide en Python :

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Insertion sort that timsort uses if the array size is small or if
the size of the "run" is small
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """Takes two sorted lists and returns a single sorted list by comparing the
    elements one at a time.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # for every i in the range of 1 to length of array
    for i in range(1, length):
        # if i is at the end of the list
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # if the i'th element of the array is less than the one before it
        if the_array[i] < the_array[i-1]:
            # if new_run is set to None (NULL)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # else if its equal to or more than
        else:
            new_run.append(the_array[i])

    # for every item in runs, append it using insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    
    # for every run in sorted_runs, merge them
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

Complexité:

Tim sort a une complexité stable de O(N log(N)) et se compare très bien à Quicksort. Une comparaison des complexités peut être trouvée sur ce tableau.

Tri par fusion

Merge Sort est un algorithme Divide and Conquer. Il divise le tableau d'entrée en deux moitiés, s'appelle pour les deux moitiés, puis fusionne les deux moitiés triées. La majeure partie de l'algorithme reçoit deux tableaux triés, et nous devons les fusionner en un seul tableau trié. L'ensemble du processus de tri d'un tableau de N entiers peut être résumé en trois étapes :

• Divisez le tableau en deux moitiés.
• Triez la moitié gauche et la moitié droite en utilisant le même algorithme récurrent.
• Fusionnez les moitiés triées.

Il existe quelque chose connu sous le nom d'algorithme à deux doigts qui nous aide à fusionner deux tableaux triés. L'utilisation de ce sous-programme et l'appel récursif de la fonction de tri par fusion sur les moitiés du tableau nous donneront le tableau trié final que nous recherchons.

Puisqu’il s’agit d’un algorithme basé sur la récursion, nous avons une relation de récurrence pour celui-ci. Une relation de récurrence est simplement une manière de représenter un problème en termes de sous-problèmes.

T(n)=2 * T(n/2) + O(n)

En termes simples, nous décomposons le sous-problème en deux parties à chaque étape et nous devons effectuer une quantité de travail linéaire pour fusionner les deux moitiés triées à chaque étape.

Complexité

Le plus grand avantage de l’utilisation du tri par fusion est que la complexité temporelle n’est que de n*log(n) pour trier un tableau entier. C'est bien mieux que le temps d'exécution n ^2 du tri à bulles ou du tri par insertion.

Avant d’écrire du code, comprenons comment fonctionne le tri par fusion à l’aide d’un diagramme.

• Initialement nous avons un tableau de 6 entiers non triés Arr(5, 8, 3, 9, 1, 2)
• Nous divisons le tableau en deux moitiés Arr1=(5, 8, 3) et Arr2=(9, 1, 2).
• Encore une fois, nous les divisons en deux moitiés : Arr3=(5, 8) et Arr4=(3) et Arr5=(9, 1) et Arr6=(2)
• Encore une fois, nous les divisons en deux moitiés : Arr7=(5), Arr8=(8), Arr9=(9), Arr10=(1) et Arr6=(2).
• Nous allons maintenant comparer les éléments de ces sous-tableaux afin de les fusionner.

Propriétés:

• Complexité spatiale : O(n)
• Complexité temporelle : O(n*log(n)). La complexité temporelle du tri par fusion peut ne pas être évidente au premier coup d'œil. Le facteur log(n) qui entre en jeu est dû à la relation de récurrence que nous avons mentionnée précédemment.
• Tri sur place : non dans une implémentation typique
• Stable : Oui
• Parallélisable : oui (Plusieurs variantes parallèles sont discutées dans la troisième édition de Cormen, Leiserson, Rivest et Stein's Introduction to Algorithms.)

Implémentation C++

void merge(int array[], int left, int mid, int right)
{
    int i, j, k;

    // Size of left sublist
int size_left = mid - left + 1;

// Size of right sublist
int size_right =  right - mid;

/* create temp arrays */
int Left[size_left], Right[size_right];

/* Copy data to temp arrays L[] and R[] */
for(i = 0; i < size_left; i++)
{
    Left[i] = array[left+i];
}

for(j = 0; j < size_right; j++)
{
    Right[j] = array[mid+1+j];
}

// Merge the temp arrays back into arr[left..right]
i = 0; // Initial index of left subarray
j = 0; // Initial index of right subarray
k = left; // Initial index of merged subarray

while (i < size_left && j < size_right)
{
    if (Left[i] <= Right[j])
    {
        array[k] = Left[i];
        i++;
    }
    else
    {
        array[k] = Right[j];
        j++;
    }
    k++;
}

// Copy the remaining elements of Left[]
while (i < size_left)
{
    array[k] = Left[i];
    i++;
    k++;
}

// Copy the rest elements of R[]
while (j < size_right)
{
    array[k] = Right[j];
    j++;
    k++;
}
}

void mergeSort(int array[], int left, int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;

        // Sort first and second halves
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);

    // Finally merge them
    merge(array, left, mid, right);
}
}

Implémentation JavaScript

function mergeSort (arr) {
  if (arr.length < 2) return arr;
  var mid = Math.floor(arr.length /2);
  var subLeft = mergeSort(arr.slice(0,mid));
  var subRight = mergeSort(arr.slice(mid));
  return merge(subLeft, subRight);
}

Nous vérifions d’abord la longueur du tableau. Si c'est 1 alors nous renvoyons simplement le tableau. Ce serait notre cas de base. Sinon, nous trouverons la valeur médiane et diviserons le tableau en deux moitiés. Nous allons maintenant trier les deux moitiés avec des appels récursifs à la fonction MergeSort.

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

Lorsque nous fusionnons les deux moitiés, nous stockons le résultat dans un tableau auxiliaire. Nous comparerons l’élément de départ du tableau de gauche à l’élément de départ du tableau de droite. Le chiffre le plus petit sera placé dans le tableau de résultats et nous le supprimerons des tableaux respectifs à l'aide de l'opérateur [shift()]. Si nous nous retrouvons toujours avec des valeurs dans le tableau de gauche ou de droite, nous les concaténerons simplement à la fin du résultat. Voici le résultat trié :

var test = [5,6,7,3,1,3,15];
console.log(mergeSort(test));

>> [1, 3, 3, 5, 6, 7, 15]

Un didacticiel YouTube pour le tri par fusion

Voici une bonne vidéo YouTube qui aborde le sujet en détail.

Implémentation en JS

const list = [23, 4, 42, 15, 16, 8, 3]

const mergeSort = (list) =>{
  if(list.length <= 1) return list;
  const middle = list.length / 2 ;
  const left = list.slice(0, middle);
  const right = list.slice(middle, list.length);
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
  var result = [];
  while(left.length || right.length) {
    if(left.length && right.length) {
      if(left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    } else if(left.length) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
  return result;
}

console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]

Implémentation en C

#include<stdlib.h> 
#include<stdio.h>
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    
    int L[n1], R[n2]; 
  
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j];
    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    {  
        int m = l+(r-l)/2; 
  
        
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
}
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Given array is \n"); 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    printf("\nSorted array is \n"); 
    printArray(arr, arr_size); 
    return 0; 

Implémentation en C++

Considérons le tableau A={2,5,7,8,9,12,13} et le tableau B={3,5,6,9,15} et nous voulons que le tableau C soit également par ordre croissant.

void mergesort(int A[],int size_a,int B[],int size_b,int C[])
{
     int token_a,token_b,token_c;
     for(token_a=0, token_b=0, token_c=0; token_a<size_a && token_b<size_b; )
     {
          if(A[token_a]<=B[token_b])
               C[token_c++]=A[token_a++];
          else
               C[token_c++]=B[token_b++];
      }
      
      if(token_a<size_a)
      {
          while(token_a<size_a)
               C[token_c++]=A[token_a++];
      }
      else
      {
          while(token_b<size_b)
               C[token_c++]=B[token_b++];
      }

}

Implémentation en Python

def merge(left,right,compare):
	result = [] 
	i,j = 0,0
	while (i < len(left) and j < len(right)):
		if compare(left[i],right[j]):
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	while (i < len(left)):
		result.append(left[i])
		i += 1
	while (j < len(right)):
		result.append(right[j])
		j += 1
	return result

def merge_sort(arr, compare = lambda x, y: x < y):
     #Used lambda function to sort array in both(increasing and decresing) order.
     #By default it sorts array in increasing order
	if len(arr) < 2:
		return arr[:]
	else:
		middle = len(arr) // 2
		left = merge_sort(arr[:middle], compare)
		right = merge_sort(arr[middle:], compare)
		return merge(left, right, compare) 

arr = [2,1,4,5,3]
print(merge_sort(arr))

Implémentation en Java

public class mergesort {

	public static int[] mergesort(int[] arr,int lo,int hi) {
		
		if(lo==hi) {
			int[] ba=new int[1];
			ba[0]=arr[lo];
			return ba;
		}
		
		int mid=(lo+hi)/2;
		int arr1[]=mergesort(arr,lo,mid);
		int arr2[]=mergesort(arr,mid+1,hi);
		return merge(arr1,arr2);
	}
	
	public static int[] merge(int[] arr1,int[] arr2) {
		int i=0,j=0,k=0;
		int n=arr1.length;
		int m=arr2.length;
		int[] arr3=new int[m+n];
		while(i<n && j<m) {
			if(arr1[i]<arr2[j]) {
				arr3[k]=arr1[i];
				i++;
			}
			else {
				arr3[k]=arr2[j];
				j++;
			}
			k++;
		}
		
		while(i<n) {
			arr3[k]=arr1[i];
			i++;
			k++;
		}
		
		while(j<m) {
			arr3[k]=arr2[j];
			j++;
			k++;
		}
		
		return arr3;
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[]= {2,9,8,3,6,4,10,7};
		int[] so=mergesort(arr,0,arr.length-1);
		for(int i=0;i<arr.length;i++)
			System.out.print(so[i]+" ");
	}

}

Exemple en Java

public class mergesort {
  public static int[] mergesort(int[] arr, int lo, int hi) {
    if (lo == hi) {
      int[] ba = new int[1];
      ba[0] = arr[lo];
      return ba;
    }
    int mid = (lo + hi) / 2;
    int arr1[] = mergesort(arr, lo, mid);
    int arr2[] = mergesort(arr, mid + 1, hi);
    return merge(arr1, arr2);
  }

  public static int[] merge(int[] arr1, int[] arr2) {
    int i = 0, j = 0, k = 0;
    int n = arr1.length;
    int m = arr2.length;
    int[] arr3 = new int[m + n];
    while (i < n && j < m) {
      if (arr1[i] < arr2[j]) {
        arr3[k] = arr1[i];
        i++;
      } else {
        arr3[k] = arr2[j];
        j++;
      }
      k++;
    }
    while (i < n) {
      arr3[k] = arr1[i];
      i++;
      k++;
    }
    while (j < m) {
      arr3[k] = arr2[j];
      j++;
      k++;
    }
    return arr3;
  }

  public static void main(String[] args) {
    int arr[] = {2, 9, 8, 3, 6, 4, 10, 7};
    int[] so = mergesort(arr, 0, arr.length - 1);
    for (int i = 0; i < arr.length; i++)
      System.out.print(so[i] + " ");
  }
}