Cette méthode algorithmique permet de résoudre un problème. Tout d'abord, on divise ce problème en une multitude de petits problèmes, puis ces sous-problèmes étant plus simples, sont ensuite résolus, et on recombine enfin les petits problèmes résolus afin d'obtenir la solution du problème de départ. (je vous invite à voir la récursivité sur laquelle cette méthode est souvent basée)

Comme son nom l'indique (ou pas), ce paradigme est séparée en trois étapes.

• DIVISER : sépare le problème initial en multiples petits problèmes.
• RÉGNER : résolus les sous-problèmes étant plus simples.
• COMBINER : assemble les solutions des sous-problèmes afin d'avoir la solution du problème initial

L'algorithme de tri-fusion est un algorithme de tri utilisant la méthode “diviser pour régner” et utilisant aussi la récursivité:

VARIABLE
A : tableau d'entiers
L : tableau d'entiers
R : tableau d'entiers
p : entier
q : entier
r : entier
n1 : entier
n2 : entier


DEBUT

FUSION (A, p, q, r):
  n1 ← q - p + 1
  n2 ← r - q
  créer tableau L[1..n1+1] et R[1..n2+1]
  pour i ← 1 à n1:
    L[i] ← A[p+i-1]
  fin pour
  pour j ← 1 à n2:
    R[j] ← A[q+j]
  fin pour
  L[n1+1] ← ∞
  R[n2+1] ← ∞
  i ← 1
  j ← 1
  pour k ← p à r:
    si L[i] ⩽ R[j]:
      A[k] ← L[i]
      i ← i + 1
    sinon:
      A[k] ← R[j]
      j ← j + 1
    fin si
  fin pour
fin FUSION

TRI-FUSION(A, p, r):
  si p < r:
    q = (p + r) / 2
    TRI-FUSION(A, p, q)
    TRI-FUSION(A, q+1, r)
    FUSION(A, p, q, r)
  fin si
fin TRI-FUSION
FIN