Mergesort est une bonne idée, car, contrairement aux autres sortes avancées, elle ne nécessite pas d'indexabilité (donc ça marche bien sur les listes chaînées aussi comme tableaux). Une introduction générale en C# est here - il n'utilise pas de génériques, et introduit inutilement des listes et des indexations où les choses pourraient parfaitement se dérouler par itération, mais je ne trouve pas d'intro élémentaire en C# bien fait. Un inconvénient dans tous les algorithmes de tri avancé est qu'il est souvent préférable, en récursion, de ne pas utiliser l'algorithme "algo avancé", mais de passer à des algorithmes plus simples pour les sous-listes suffisamment petites - les algorithmes simples ont pire big-O, mais de plus petites constantes multiplicatives, de sorte que le mélange peut souvent être optimal.
Une variante intéressante est natural mergesort, qui tire parti des exécutions qui peuvent déjà être présentes dans les données - l'URL que j'ai donné utilise pseudocode, mais il est très lisible. Mergesort naturel est idéal pour les données qui sont déjà triées, mais avec quelques éléments en panne, par ex. ajouté à la fin - il peut offrir des performances O (N) asymptotiques lorsque les quelques éléments sont en effet peu nombreux ;-).