Les tris à connaître

Trier coûte O(n log n) et ouvre la porte à la recherche binaire, aux deux pointeurs et aux intervalles.

En pratique on utilise le tri de la bibliothèque standard ; en entretien, il faut savoir expliquer fusion et rapide, et leurs compromis.

Tri fusion#

Diviser en deux moitiés, trier chacune, puis fusionner deux listes déjà triées en une passe.

function mergeSort(nums: number[]): number[] {
  if (nums.length <= 1) return nums;
  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));
  const merged: number[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    merged.push(left[i] <= right[j] ? left[i++] : right[j++]);   // <= : tri stable
  }
  return merged.concat(left.slice(i), right.slice(j));
}

Tri rapide#

Choisir un pivot, placer les plus petits à gauche et les plus grands à droite, puis trier chaque côté récursivement. Version courte (hors place) :

function quickSort(nums: number[]): number[] {
  if (nums.length <= 1) return nums;
  const pivot = nums[nums.length >> 1];
  const less = nums.filter((x) => x < pivot);
  const equal = nums.filter((x) => x === pivot);
  const greater = nums.filter((x) => x > pivot);
  return [...quickSort(less), ...equal, ...quickSort(greater)];
}

Piège : ne comparez jamais avec x - y dans un comparateur : le résultat peut déborder. En JavaScript, arr.sort() sans comparateur trie par ordre alphabétique ([10, 9, 1].sort() donne [1, 10, 9]) : passez toujours (a, b) => a - b.

Cas pratique : « fusionner des intervalles » ou « deux éléments les plus proches » se résolvent presque toujours en triant d'abord, puis en un seul passage. Le tri (O(n log n)) domine alors la complexité totale.