algorithme de tri externe

Un algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur. Recourir à la mémoire externe permet d'arriver à trier des volumes de données plus importants mais induit de nouvelles difficultés, le temps d'accès aux données étant beaucoup plus long. Aller chercher chaque valeur sur le disque lorsque l'on en a besoin serait trop lent ; en pratique, les approches qui fonctionnent travaillent successivement sur différentes parties des données chargées temporairement dans la mémoire principale. Les algorithmes de tri externe sont donc typiquement des variantes du tri fusion, qui s'adapte bien à ces contraintes : l'entrée est divisée en sous-ensembles pouvant être chargés un à un en mémoire, triés puis réécris dans des fichiers temporaires qui sont ensuite fusionnés.