Diviser pour régner

$T(n)=\Theta (n\log n)$, dans le meilleur comme dans le pire cas.

$\Theta (n)$ d'espace supplémentaire — la fusion construit une nouvelle liste. C'est son seul défaut face au tri rapide, qui trie en place mais dégénère en $O(n^2)$ sur les pires entrées, et face au tri par tas (chapitre chap:tas), qui est en place et $\Theta (n\log n)$ garanti.

Une inversion d'un tableau est un couple $(i,j)$ avec $i<j$ et $t_i>t_j$. Leur nombre mesure le désordre : nul si le tableau est trié, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ s'il est à l'envers.

La force brute est $\Theta (n^2)$. Or la fusion les compte gratuitement : quand on prend un élément de la moitié droite alors qu'il reste $r$ éléments à gauche, cet élément est plus petit que ces $r$-là, tous situés avant lui — soit $r$ inversions d'un coup.

(* Coupe l en ses n/2 premiers et le reste. CONTIGUË, contrairement au
   « couper » du tri : le comptage exige que TOUTE la moitié gauche précède
   la droite dans la liste d'origine. *)
let couper_contigu l =
  let n = List.length l / 2 in
  let rec aux k = function
    | r when k = 0 -> ([], r)
    | x :: r -> let (a, b) = aux (k - 1) r in (x :: a, b)
    | [] -> ([], [])
  in aux n l

(* Renvoie (liste triée, nombre d'inversions). Complexité : Theta(n log n). *)
let rec tri_compte = function
  | ([] | [_]) as l -> (l, 0)
  | l ->
      let (g, d) = couper_contigu l in
      let (g', ig) = tri_compte g and (d', id) = tri_compte d in
      let rec fusion a na b =
        match a, b with
        | [], l -> (l, 0)
        | l, [] -> (l, 0)
        | x :: ra, y :: rb ->
            if x <= y then let (f, k) = fusion ra (na - 1) b in (x :: f, k)
            else
              (* y passe devant TOUS les éléments restants de a. On transporte
                 leur nombre en argument : « List.length a » ici rendrait la
                 fusion quadratique, et donc l'algorithme entier. *)
              let (f, k) = fusion a na rb in (y :: f, k + na)
      in
      let (f, ifus) = fusion g' (List.length g') d' in
      (f, ig + id + ifus)

Le même découpage, le même coût, une information de plus. C'est la marque d'une bonne méthode : on l'adapte sans la refaire.

Étant donné $n$ entiers et une cible $c$, existe-t-il un sous-ensemble de somme $c$ ?

(* Vrai s'il existe un sous-ensemble de t de somme c. Complexité : O(2^(n/2) · n). *)
let somme_sous_ensemble t c =
  let n = Array.length t in
  let moitie = n / 2 in
  (* toutes les sommes atteignables avec les éléments d'indices [d, f[ *)
  let sommes d f =
    let acc = ref [0] in
    for i = d to f - 1 do
      acc := !acc @ List.map (fun s -> s + t.(i)) !acc
    done;
    !acc
  in
  let a = sommes 0 moitie in
  let b = List.sort compare (sommes moitie n) in
  let tab = Array.of_list b in
  (* pour chaque somme de la première moitié, on CHERCHE son complément
     dans la seconde, par DICHOTOMIE : c'est la « rencontre » *)
  List.exists (fun s -> recherche tab (c - s) <> None) a

Le gain, chiffré. Pour $n=40$ : l'exhaustif fait $2^{40}\approx 1,1\cdot 10^{12}$ opérations — dix-huit minutes. La rencontre au milieu en fait $2^{20}\approx 10^6$ de chaque côté, plus le tri et les recherches : quelques dixièmes de seconde. Le même problème, quatre ordres de grandeur d'écart.

Étant donné $n$ points du plan, trouver la paire la plus proche. La force brute examine les $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ paires : $\Theta (n^2)$.

Diviser : on trie les points par abscisse et l'on coupe par une droite verticale médiane. Régner : on résout à gauche et à droite, obtenant $\delta =\min ({\delta }_g,{\delta }_d)$. Combiner : il reste à examiner les paires à cheval sur la droite. Seuls comptent les points situés dans la bande de largeur $2\delta$ centrée sur la coupure — et, une fois cette bande triée par ordonnée, chaque point n'a besoin d'être comparé qu'à un nombre borné de suivants, car deux points de la bande distants de plus de $\delta$ verticalement ne peuvent pas faire mieux que $\delta$.

Complexité : $T(n)=2T(n/2)+\Theta (n)$, soit $\Theta (n\log n)$ — la bande se traite en temps linéaire une fois les points triés par ordonnée.