Cet algorithme de tri a été proposé par le Dr Oyelami Olufemi Moses qui l'a - modestement - appelé Oyelami's Sort.
L'idée est, encore une fois, de corriger le problème des "tortues" du tri à bulle. Le Dr Oyelami Olufemi propose d'utiliser un tri cocktail classique mais en le faisant précéder d'une phase inspirée du tri par la méthode de Batcher. Vous en trouverez une description (en anglais) ici.
L'algorithme divise donc les éléments à trier dans des sous-séquences (comme pour un tri de Shell), mais en comparant le premier élément avec le dernier et en les permutant si le premier est supérieur au dernier. Ensuite l'algorithme compare le second avec l'avant dernier et les permutte éventuellement, puis le troisième avec l'antépénultième etc...
Ce processus se poursuit jusqu'à ce que les deux derniers éléments intermédiaires consécutifs soient comparées ou jusqu'à ce qu'il reste un seul élément dans le milieu.
Après cela, c'est un tri bulle bidirectionnel qui est appliquée pour trier les éléments adjacents.
Cette approche réduit légérement le nombre de comparaisons et d'inversions effectuées.
L'animation ci-après détaille le fonctionnement de ce tri :
Si on retient la méthode du Oyelami pour le petit jeu page précédente, on a :
Ce tri n'est pas stable, comme vous pouvez le vérifier ici.
Les performances de ce tri sont certes meilleures que celles d'un tri à bulle classique, et même que celles d'un tri cocktail ou d'un tri Gnome mais restent bien inférieures à celles d'un tri à peigne ou d'un tri Shell.
L'algorithme du Dr Oyelami Olufemi n'a donc rien de révolutionnaire. Il s'agit d'une petite amélioration du tri bulle dont le principal intérêt réside dans sa facilité de codage.