はじめに

Qiita 記事は初投稿となります。いろいろとおかしな点もあるかもしれません。
さて、TwitterでC#における OrderByとSortのパフォーマンスの違いの話になって、自分もどれくらいの差があるのか把握していなかったので、検証して、せっかくなので記事に残すことにしました。

環境

この記事では、以下の環境を使用しました。
Windows 10 Home
Intel Core i5 6400T
.NET Framework 4.6.1
Visual Studio 2019 Debug環境

検証方法

元の配列は、0から(10^6 - 1)を昇順に並べた、100万要素の配列とする。
Array.Sort(array) List<T>.Sort() enumerable.OrderBy(x => x) それぞれについて、ソートを10回行う。

以下に記載してある時間は「ミリ秒単位」で「ソート10回分」です。(1回あたりは10で割ってください。)

ランダム順の配列を並び替え

以下の操作を10回行い、ソート10回にかかった時間の平均値・最大値・最小値を計算します。

元の配列をランダム順に並び替える。
それぞれのソート関数でソートを実行する。

結果

	Array.Sort	List.Sort	OrderBy
Max	1721ms	1448ms	5428ms
Min	1307ms	1301ms	5177ms
Ave	1375.5ms	1347.7ms	5306.7ms

ランダム順では、List.Sort が Array.Sortよりわずかに早く、OrderBy はそれらより4倍近く遅い結果となりました。

昇順・降順の配列を並び替え

以下の操作それぞれで、ソート10回にかかった時間を計算します。

昇順となっている（すでにソートされている）配列に対してソートを実行する。
降順となっている配列に対してソートを実行する。

結果

	Array.Sort	List.Sort	OrderBy
昇順	175ms	184ms	2608ms
降順	368ms	313ms	1923ms

昇順配列におけるソートでは、 Array.Sort が List.Sort よりわずかに早く、 OrderBy はそれらより15倍近く(!)遅い結果となりました。
降順配列におけるソートでは、 List.Sort が Array.Sort より少し早く、 OrderBy はそれらより6倍近く遅い結果となりました。

それぞれの関数別にみると、
Array.Sort では、昇順配列におけるソートが降順配列におけるソートより約2倍早く、ランダム配列におけるソートより約8倍早い。
List.Sort では、昇順配列におけるソートが降順配列におけるソートより約1.7倍早く、ランダム配列におけるソートより約7.3倍早い。
OrderBy では、昇順配列におけるソートが降順配列におけるソートより約1.3倍遅く、ランダム配列におけるソートより約2倍早いという結果になりました。

まとめ

今回の検証に使用したコードは、 Gistに載せています。

数値や文字列などの、オブジェクト自体の並び替えには、絶対に Array.Sort や List<T>.Sort() を使いましょう!! (特に私は競技プログラミングをやっていて、数百ミリ秒でも早いほうがいいため、今後はSortを使うことをより意識しようと思います。ソートが原因でTLEはくらいたくない!!)
今回は検証していませんが、オブジェクトのプロパティを指定した並び替えでも、objects.OrderBy(x => x.Target); とするよりも、ToArray() → Array.Sort(objectsArray, (a, b) => a.Target.CompareTo(b.Target); としたほうが高速だと思います。
OrderBy は、IEnumerable<T> を対象に並び替えができるようになっているため、遅い実装になっているんですかね…。

もしかしたら遅延評価の問題などで、OrderBy のほうが高速になることがあるかもしれません。 (特に EnumerateFiles などで外部にアクセスするとき)

この記事について、ご意見やご指摘などがありましたら、記事のコメント等へお願いいたします。