(2017/09/10 パフォーマンス比較にOrderByを追加。それに伴い、結論をやや修正)
ListとLinkedListの挿入ソートおよびマージソートを実装します。どちらも安定ソートです。
何を考えて実装したのか、長々と別の記事に書いてあるので、興味があればそっちもよろしくです。
マージソートを単純に実装するより、対象となる要素数が少ない時は挿入ソートのほうが速いので、挿入ソートに差し替える対応をします。なので、マージソートの実装がメインで、最適化の副産物で挿入ソートもあるよ、という感じです。