ここでは複合型を含むコレクションのソートについて見ていきます。

§1 複合型のソート

数値や文字列などの型は、あらかじめデフォルトの並べ替え順序が定義されているため特に何も指定しなくてもArray.SortやList.Sortなどのメソッドでソートを行うことが出来ます。 一方、独自に定義したクラス・構造体などの複合型(1つ以上の基本型を組み合わせて構成される型)の場合は、並べ替え順序を個別に定義しない限りソートすることが出来ません。

仮に型が比較演算子をオーバーロードしていてもそれだけではソート出来るようにはなりません。 この点については、比較演算子のオーバーロードとIComparable<T>インターフェイスで詳しく解説しています。

ここでは、複合型をソートする方法・並べ替え順序を定義する方法について解説します。

§1.1 Sort + Comparison<T>

降順でのソートでも述べているとおり、Array.SortメソッドおよびList.Sortメソッドでは、並び替え順序を定義したメソッドを用意し、それをComparison<T>デリゲートとしてSortメソッドの引数に指定することにより、デフォルト(昇順)以外の順序、独自に定義した順序でソートすることが出来ます。

早速、独自に定義したクラスをソートする方法、並べ替え順序を定義する方法について順を追って見ていきます。

ここではNameフィールド(string)とIDフィールド(int)を持つクラスAccountを作成し、Accountクラスのインスタンスが格納されたリストをID順にソートすることにします。 具体的には、次の不完全なコードでソートが出来るように実装していきます。

以下のコードで複合型のコレクションをソートできるようにしたい
using System;
using System.Collections.Generic;

class Account {
  public int ID;
  public string Name;

  public Account(int id, string name)
  {
    this.ID = id;
    this.Name = name;
  }
}

class Sample {
  static void Main()
  {
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob"),
      new Account(1, "Dave"),
      new Account(2, "Alice"),
      new Account(5, "Charlie"),
      new Account(4, "Eve"),
    });

    // このままではソート出来ない (InvalidOperationExceptionがスローされる)
    // list.Sort();

    foreach (Account a in list) {
      Console.WriteLine("{0} {1}", a.ID, a.Name);
    }
  }
}

まずは、並べ替え順序を定義をするために、比較を行うメソッドを用意します。 このメソッドは、Comparison<T>デリゲートの形でSortメソッドに渡す必要があります。 Comparison<T>デリゲートの形式を見てみると、次のようになっています。

Comparison<T>デリゲートのシグネチャ
public delegate int Comparison<in T>(T x, T y);

この形式を分かりやすく説明すると、「ある型Tの要素二つを比べて、どちらが小さいか・大きいかをintの数値で返す」というものです。 Sortメソッドの内部では、各要素の比較が行われる度にこのメソッドが呼び出され、戻り値として返される大小関係によって要素の並べ替えが行われることになります。 この形式にあわせて、Accountクラスを比較するメソッドCompareAccountのひな形を作成すると次のようになります。

Accountクラスの比較を行うメソッドのひな形
static int CompareAccount(Account x, Account y)
{
  return 0; // xとyを比較した結果を返す
}

次にこのメソッドを実装します。 比較を行うメソッドでは二つの要素の大小関係を戻り値として返します。 具体的には、引数として渡される二つの要素xyについて、その大小関係が

  • x > y (xyより大きい) ならば 正の数
  • x < y (xyより小さい) ならば 負の数
  • x = y (xyが等しい) ならば 0

を返すようにします。 このルールに従ってメソッドを実装すると、次のようになります。 正の数・負の数ならなんでもよいので、ここではそれぞれ1-1を返しています。

大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッドのひな形
static int CompareAccount(Account x, Account y)
{
  if (x > y)
    return 1; // xがyより大きい
  else if (x < y)
    return -1; // xがyより小さい
  else // if (x == y)
    return 0; // xとyが等しい
}

当然Accountクラスのインスタンスそのものを比較することはできないため、このままでは不十分です。 ここではID順でのソートを行いたいため、インスタンスの大小関係がIDフィールドの値によって定まるように実装します。 最終的に、ID順でソートするためのメソッドCompareAccountは次のようになります。

IDフィールドの値に従って大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッド
static int CompareAccount(Account x, Account y)
{
  if (x.ID > y.ID)
    return 1; // xのIDがyのIDより大きい→xはyより大きい
  else if (x.ID < y.ID)
    return -1; // xのIDがyのIDより小さい→xはyより小さい
  else // if (x.ID == y.ID)
    return 0; // xのIDとyのIDが等しい→xはyと等しい
}

最後に、このメソッドをSortメソッドの引数として渡せば、リストはこのメソッドで定義された順序、すなわちID順にソートされるようになります。

Accountクラスの比較を行うメソッドを追加してAccountのリストをソートできるようにしたコード
using System;
using System.Collections.Generic;

class Account {
  public int ID;
  public string Name;

  public Account(int id, string name)
  {
    this.ID = id;
    this.Name = name;
  }
}

class Sample {
  // IDプロパティの値にしたがってAccountクラスの比較を行うメソッド
  static int CompareAccount(Account x, Account y)
  {
    if (x.ID > y.ID)
      return 1;
    else if (x.ID < y.ID)
      return -1;
    else // if (x.ID == y.ID)
      return 0;
  }

  static void Main()
  {
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob"),
      new Account(1, "Dave"),
      new Account(2, "Alice"),
      new Account(5, "Charlie"),
      new Account(4, "Eve"),
    });

    // 比較用のメソッドを指定してソート
    list.Sort(CompareAccount);

    foreach (Account a in list) {
      Console.WriteLine("{0} {1}", a.ID, a.Name);
    }
  }
}
実行結果
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie

名前順にソートしたければ、Nameフィールドの値を比較するようにCompareAccountメソッドの実装を変えるだけで出来ます。 なお、文字列の比較はその都度定義しなくても、既に用意されているString.Compareメソッドを使うことが出来ます。

Nameフィールドの値に従って大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッド
static int CompareAccount(Account x, Account y)
{
  // string.Compareメソッドを使って2つのNameフィールドの値の大小関係を取得し、
  // それをAccountクラスの大小関係として返す
  return string.Compare(x.Name, y.Name);
}
実行結果
2 Alice
3 Bob
5 Charlie
1 Dave
4 Eve

このように、並べ替え順序(大小関係)を定義することができ、Comparison<T>デリゲートの形式でSortメソッドに渡すことができれば、どのような複合型でもソートを行うことが出来るようになります。

なお、ここまでは昇順となるようにしてきましたが、降順にしたければCompareAccountで定義する大小関係を逆にするか、Reverseメソッドを使ってソートした後で逆順にするだけです。

降順でのソートについては基本型のソートと昇順・降順でのソート §.降順でのソートを参照してください。

文字列の比較やString.Compareメソッドの詳細に関しては文字列の探索・比較 §.文字列の比較・等価性の検証を参照してください。

§1.1.1 null/Nothingの考慮

ソートしたい対象が参照型のコレクションで、かつコレクションにnull/Nothingが含まれる可能性がある場合は、比較を行うメソッドにおいてもnull/Nothingだった場合の考慮を行う必要があります。 具体的には次のようにnull/Nothingとの比較を行うコードを追加します。

引数にnullが渡される可能性のある比較メソッドの実装例
static int CompareAccount(Account x, Account y)
{
  if (x == y)
    return 0; // 同一のインスタンス、またはどちらもnullの場合、xとyは等しいものとする
  else if (x == null)
    return -1; // xがnull、かつyがnull以外の場合、xはyより小さいものとする
  else if (y == null)
    return 1; // yがnull、かつxがnull以外の場合、xはyより大きいものとする

  // どちらもnull以外の場合、IDプロパティの値で比較する
  if (x.ID > y.ID)
    return 1;
  else if (x.ID < y.ID)
    return -1;
  else // if (x.ID == y.ID)
    return 0;
}

.NET Frameworkにおける文字列型(Stringクラス)では、null/Nothingは他のいずれの値よりも小さい、またnull/Nothing同士は等しいものとして比較が行われるため、上記の例もこれに準じた結果を返すようにしています。

以下は上記のように定義した比較メソッドを使ってnull/Nothingを含むコレクションをソートする例です。

List.Sortメソッドでnullを含むコレクションをソートする
using System;
using System.Collections.Generic;

class Account {
  public int ID;
  public string Name;

  public Account(int id, string name)
  {
    this.ID = id;
    this.Name = name;
  }
}

class Sample {
  // IDプロパティの値にしたがってAccountクラスの比較を行うメソッド
  static int CompareAccount(Account x, Account y)
  {
    if (x == y)
      return 0; // 同一のインスタンス、またはどちらもnullの場合、xとyは等しいものとする
    else if (x == null)
      return -1; // xがnull、かつyがnull以外の場合、xはyより小さいものとする
    else if (y == null)
      return 1; // yがnull、かつxがnull以外の場合、xはyより大きいものとする

    // どちらもnull以外の場合、IDプロパティの値で比較する
    if (x.ID > y.ID)
      return 1;
    else if (x.ID < y.ID)
      return -1;
    else // if (x.ID == y.ID)
      return 0;
  }

  static void Main()
  {
    // 要素にnullを含むコレクション
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob"),
      new Account(1, "Dave"),
      new Account(2, "Alice"),
      null,
      new Account(5, "Charlie"),
      null,
      new Account(4, "Eve"),
    });

    // 比較用のメソッドを指定してソート
    list.Sort(CompareAccount);

    foreach (Account a in list) {
      if (a == null)
        Console.WriteLine("(null)");
      else
        Console.WriteLine("{0} {1}", a.ID, a.Name);
    }
  }
}
実行結果
(null)
(null)
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie

このように、昇順の場合はnull/Nothingが前の方へ並べ替えられます。 後ろの方へ並べ替えたい場合は、比較メソッドを変更してnull/Nothingは他のいずれの値よりも大きいと定義することによって実現できます。

§1.2 OrderBy

複合型は1つ以上の基本型から構成されるため、複合型のソートで実際にキーとして選ばれるのは単純型のメンバとなります。 また、単純型のソートの場合でも、単に昇順・降順でのソートで十分な場合がほとんどで、独自の並び替え順序が必要になる事はそう多くありません。

OrderByメソッドは、複合型をソートしたい場合でもキーとなるメンバを選択するだけでソートすることが出来、また選択したキーが単純型であれば並べ替え順序を定義する必要もないため、より少ない記述でソートを行うことが出来ます。

OrderByメソッドの詳細とキーの選択については基本型のソートと昇順・降順でのソート §.OrderByメソッドとキーの選択で解説しているので省略しますが、先に挙げた例をList.SortではなくOrderByメソッドでソートするように変えると、以下のようになります。

OrderByメソッドを使って複合型のコレクションをソートする
using System;
using System.Collections.Generic;
using System.Linq;

class Account {
  public int ID;
  public string Name;

  public Account(int id, string name)
  {
    this.ID = id;
    this.Name = name;
  }
}

class Sample {
  static void Main()
  {
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob"),
      new Account(1, "Dave"),
      new Account(2, "Alice"),
      new Account(5, "Charlie"),
      new Account(4, "Eve"),
    });

    // IDでソート(IDフィールドをソート時のキーとしてOrderByで並べ替える)
    IOrderedEnumerable<Account> sorted = list.OrderBy(a => a.ID);
    // Nameでソートする場合(Nameフィールドをソート時のキーとしてOrderByで並べ替える)
    //IOrderedEnumerable<Account> sorted = list.OrderBy(a => a.Name);

    foreach (Account a in sorted) {
      Console.WriteLine("{0} {1}", a.ID, a.Name);
    }
  }
}
実行結果
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie

OrderByメソッドの代わりにOrderByDescendingメソッドを使うことにより、降順でソートすることが出来ます。

§1.2.1 null/Nothingの考慮

OrderByメソッドではキーの選択を行ってソートを行います。 コレクション内の要素がnull/Nothingだった場合にはキーとして使う値を参照しようとしてもヌル参照となるため、ソートを継続することができません。 そのため、ソートしたい対象が参照型のコレクションで、かつコレクションにnull/Nothingが含まれる可能性がある場合は、要素がnull/Nothingだった場合の考慮を行う必要があります。

具体的には、次のようにして非nullの要素のみをソートするようにします。

  1. コレクション内の要素のうち、nullの要素とそうでないものを分ける (Whereメソッド)
  2. 非nullの要素のみソートを行う (OrderByメソッド)
  3. nullの要素と、ソートした非nullの要素を結合する (Concatメソッド)

以下は上記のようにしてnull/Nothingを含むコレクションをソートする例です。

OrderByメソッドでnullを含むコレクションをソートする
using System;
using System.Collections.Generic;
using System.Linq;

class Account {
  public int ID;
  public string Name;

  public Account(int id, string name)
  {
    this.ID = id;
    this.Name = name;
  }
}

class Sample {
  static void Main()
  {
    // 要素にnullを含むコレクション
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob"),
      new Account(1, "Dave"),
      new Account(2, "Alice"),
      null,
      new Account(5, "Charlie"),
      null,
      new Account(4, "Eve"),
    });

    // コレクションのうち、nullの要素のみを取得する
    IEnumerable<Account> nulls = list.Where(a => a == null);

    // コレクションのうち、非nullの要素のみを取得する
    IEnumerable<Account> nonNulls = list.Where(a => a != null);

    // nullの要素と、ソートした非nullの要素を結合する
    IEnumerable<Account> sorted = nulls.Concat(nonNulls.OrderBy(a => a.ID));

    foreach (Account a in sorted) {
      if (a == null)
        Console.WriteLine("(null)");
      else
        Console.WriteLine("{0} {1}", a.ID, a.Name);
    }
  }
}
実行結果
(null)
(null)
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie

この例ではnull/Nothingを先に結合しているため、null/Nothingが前の方へ並べ替えられます。 後ろの方へ並べ替えたい場合は、次のように結合順序を逆にすることで実現できます。

OrderByメソッドでnullを後ろの方へ並べるようにソートする
// ソートした非nullの要素の後にnullの要素を結合する
IEnumerable<Account> sorted = nonNulls.OrderBy(a => a.ID).Concat(nulls);


§2 複数キーでのソート

ここでは複数のキーでソートする場合についてを扱います。 たとえば、次のようなデータがあったときに、まずAge(年齢)の若い順に並べ替え、Ageが同じ場合はIDが小さい順に並べ替えたいといった場合です。 言い換えると、Ageを第一のキー、IDを第二のキーとしてソートするための方法です。

ソート前のデータ
ID Name Age
3 Bob 16
1 Dave 25
2 Alice 16
5 Charlie 9
4 Eve 16
6 Romeo 9
7 Juliet 25

→ソート→

得たい結果
ID Name Age
5 Charlie 9
6 Romeo 9
2 Alice 16
3 Bob 16
4 Eve 16
1 Dave 25
7 Juliet 25

§2.1 Sort + Comparison<T>

これまでの例では、並べ替え順序を定義する際に単一のキーのみを用いていましたが、並べ替え順序の定義を拡張することで複数のキーでソートできるようになります。 複数のキーでソートするには、まず第一のキーで比較し、同じだった場合は第二のキーで比較するように並べ替え順序を定義することで実現できます。

まず、一つのキーでソートする場合について振り返ると、比較を行うメソッドでは引数として渡される二つの要素xyについて、その大小関係に従って次のような値を返すように実装する必要がありました。

  • x > y ならば 正の数
  • x < y ならば 負の数
  • x = y ならば 0

二つのキーでソートする場合は、要素xyについてまず第一のキーで比較を行い、第一のキーが同じだった場合は第二のキーで比較するようにします。 つまり、上記の条件式を拡張して、比較を行うメソッドでは次のような値を返すように実装します。

  • 第一のキーについて x > y (x.Key1 > y.Key1) ならば 正の数
  • 第一のキーについて x < y (x.Key1 < y.Key1) ならば 負の数
  • 第一のキーについて x = y (x.Key1 = y.Key1) ならば さらに第二のキーで比較する
    • 第二のキーについて x > y (x.Key2 > y.Key2) ならば 正の数
    • 第二のキーについて x < y (x.Key2 < y.Key2) ならば 負の数
    • 第二のキーについて x < y (x.Key2 = y.Key2) ならば 0

このようにすることで、各要素はまず第一のキーの順に並べ替えられ、第一のキーが同じ要素については第二のキーの順に並べ替えられるようになり、二つのキーでソートされることになります。

具体例を見ていきます。 次の例では、ID(int)、名前(string)、年齢(int)のフィールドを持つAccountクラスとそれを格納するリストを作成し、ソートしています。 ここでは第一のキーを年齢、第二のキーをIDとし、年齢が若い順、年齢が同じ場合はIDが小さい順にソートしています。

Sortメソッドで複数キーのソートを行う
using System;
using System.Collections.Generic;

class Account {
  public int ID;
  public string Name;
  public int Age;

  public Account(int id, string name, int age)
  {
    this.ID = id;
    this.Name = name;
    this.Age = age;
  }
}

class Sample {
  static int CompareAccount(Account x, Account y)
  {
    // 第一のキー(Ageフィールド)で比較
    if (x.Age > y.Age) {
      return 1;
    }
    else if (x.Age < y.Age) {
      return -1;
    }
    else /* if (x.Age == y.Age) */ {
      // 第一のキーが同じだった場合は、第二のキー(IDフィールド)で比較
      if (x.ID > y.ID)
        return 1;
      else if (x.ID < y.ID)
        return -1;
      else // if (x.ID == y.ID)
        return 0;
    }
  }

  static void Main()
  {
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob", 16),
      new Account(1, "Dave", 25),
      new Account(2, "Alice", 16),
      new Account(5, "Charlie", 9),
      new Account(4, "Eve", 16),
      new Account(6, "Romeo", 9),
      new Account(7, "Juliet", 25),
    });

    // ソート
    list.Sort(CompareAccount);

    foreach (Account a in list) {
      Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age);
    }
  }
}
実行結果
5 Charlie  9
6 Romeo    9
2 Alice    16
3 Bob      16
4 Eve      16
1 Dave     25
7 Juliet   25

次に上記の例を少し変えて、名前を第一のキー、IDを第二のキーとしてソートしてみます。 文字列の比較にはString.Compareメソッドが使えます。 このメソッドも引数の大小関係に応じて正の数・負の数・0のいずれかが返されます。 同じ場合には0となるので、戻り値が0の場合は第二のキーで比較するようにします。

Sortメソッドで複数キーのソートを行う(第一キーと第二キーの順序を替えたもの)
using System;
using System.Collections.Generic;

class Account {
  public int ID;
  public string Name;
  public int Age;

  public Account(int id, string name, int age)
  {
    this.ID = id;
    this.Name = name;
    this.Age = age;
  }
}

class Sample {
  static int CompareAccount(Account x, Account y)
  {
    // 第一のキー(Nameフィールド)で比較
    int compareName = string.Compare(x.Name, y.Name);

    if (compareName == 0) {
      // x.Name == y.Nameだった場合、第二のキー(IDフィールド)で比較する
      if (x.ID > y.ID)
        return 1;
      else if (x.ID < y.ID)
        return -1;
      else // if (x.ID == y.ID)
        return 0;
    }
    else {
      // x.Name > y.Nameもしくはx.Name < y.Nameだった場合、比較結果をそのまま返す
      return compareName;
    }
  }

  static void Main()
  {
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Alice", 16),
      new Account(1, "Bob", 25),
      new Account(2, "Alice", 16),
      new Account(5, "Charlie", 9),
      new Account(4, "Bob", 16),
      new Account(6, "Alice", 9),
      new Account(7, "Charlie", 25),
    });

    // ソート
    list.Sort(CompareAccount);

    foreach (Account a in list) {
      Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age);
    }
  }
}
実行結果
2 Alice    16
3 Alice    16
6 Alice    9
1 Bob      25
4 Bob      16
5 Charlie  9
7 Charlie  25

ここまではキーが二つの場合を例示しましたが、さらに多くのキーでソートしたければ、第二のキーで比較して同じなら第三のキー、第三のキーで比較して同じなら第四のキーと、比較処理を次々拡張することで実現できます。

§2.2 OrderBy + ThenBy

OrderByメソッドのみを使ったソートでは単一のキーでしかソート出来ませんが、ThenByメソッドと組み合わせて使うと、複数のキーでのソートが出来るようになります。

ThenByメソッドは、OrderByメソッドの戻り値であるIOrderedEnumerable<TSource>に対する拡張メソッドであり、OrderByメソッドの結果(単一のキーでソートした結果)に対してThenByメソッドを呼び出すことにより、第二のキーでソートした結果を得ることが出来ます。

早速、具体例を見ていきます。 次の例では、ID(int)、名前(string)、年齢(int)のフィールドを持つAccountクラスとそれを格納するリストを作成し、ソートしています。 ここでは第一のキーを年齢、第二のキーをIDとし、年齢が若い順、年齢が同じ場合はIDが小さい順にソートしています。

OrderBy+ThenByメソッドで複数キーのソートを行う
using System;
using System.Collections.Generic;
using System.Linq;

class Account {
  public int ID;
  public string Name;
  public int Age;

  public Account(int id, string name, int age)
  {
    this.ID = id;
    this.Name = name;
    this.Age = age;
  }
}

class Sample {
  static void Main()
  {
    List<Account> list = new List<Account>(new Account[] {
      new Account(3, "Bob", 16),
      new Account(1, "Dave", 25),
      new Account(2, "Alice", 16),
      new Account(5, "Charlie", 9),
      new Account(4, "Eve", 16),
      new Account(6, "Romeo", 9),
      new Account(7, "Juliet", 25),
    });

    // ソート
    // (AgeをキーとしてOrderByにより並べ替え、その結果をさらにIDをキーとしてThenByで並べ替える)
    IOrderedEnumerable<Account> sorted = list.OrderBy(a => a.Age).ThenBy(a => a.ID);

    foreach (Account a in sorted) {
      Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age);
    }
  }
}
実行結果
5 Charlie  9
6 Romeo    9
2 Alice    16
3 Bob      16
4 Eve      16
1 Dave     25
7 Juliet   25

さらに、ThenByメソッドの戻り値もIOrderedEnumerable<TSource>であるため、ThenByメソッドの戻り値に対してThenByメソッドを呼び出すと、第三のキーでソートした結果を得られるようになります。 このように、キーの数に応じてThenByメソッドを続けて呼び出すことで複数キーでのソートを行うことが出来ます。

OrderByメソッドと同様、ThenByメソッドも遅延実行されるため、戻り値に対してforeach等で列挙操作を行うことで初めてソートが行われる点に注意してください。

§3 パフォーマンスの比較

ここではソートを行ういくつかのケースについてパフォーマンスの比較を行った結果を紹介します。 比較メソッドの定義方法やソートするデータの種類等によっては結果が変わるので、ここで紹介している結果はあくまで参考程度のものです。

§3.1 Sort vs OrderBy

複数のキーでソートするのに、Sort(Comparison<T>)メソッドを使った場合とOrderByメソッド+ThenByメソッドを使った場合を比較すると、速度の点では大きな差は無いようです。 以下のコードでは、先と同様100個、10,000個、1,000,000個の要素を持つList<Tuple<int, int>>に対してSort(Comparison<T>)メソッドとOrderByメソッド+ThenByメソッドでソートし、列挙する操作をそれぞれ3回試行した場合の経過時間を比較しています。

検証に使ったコード
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Sample {
  static void Main()
  {
    Console.WriteLine(Environment.OSVersion);
    Console.WriteLine(Environment.Version);

    foreach (var count in new[] {100, 10 * 1000, 1000 * 1000}) {
      Console.WriteLine("{0:N0}", count);

      for (var i = 0; i < 3; i++) {
        TestSortComparison(CreateSource(count, i));
        TestOrderByThenBy(CreateSource(count, i));
      }
    }
  }

  static List<Tuple<int, int>> CreateSource(int count, int seed)
  {
    var rand = new Random(seed);
    var list = new List<Tuple<int, int>>();

    for (var i = 0; i < count; i++) {
      list.Add(Tuple.Create(rand.Next(), rand.Next()));
    }

    return list;
  }

  static int Compare(Tuple<int, int> x, Tuple<int, int> y)
  {
    var ret = x.Item1 - y.Item1;

    return ret == 0 ? x.Item2 - y.Item2 : ret;
  }

  static void TestSortComparison(List<Tuple<int, int>> source)
  {
    var sw = Stopwatch.StartNew();

    source.Sort(Compare);

    foreach (var val in source) {
    }

    sw.Stop();

    Console.WriteLine("  Sort(Comparison<T>): {0}", sw.Elapsed);
  }

  static void TestOrderByThenBy(List<Tuple<int, int>> source)
  {
    var sw = Stopwatch.StartNew();

    foreach (var val in source.OrderBy(val => val.Item1).ThenBy(val => val.Item2)) {
    }

    sw.Stop();

    Console.WriteLine("  OrderBy + ThenBy   : {0}", sw.Elapsed);
  }
}
実行結果 (Windows 7 + .NET Framework 4)
Microsoft Windows NT 6.1.7601 Service Pack 1
4.0.30319.239
100
  Sort(Comparison<T>): 00:00:00.0016116
  OrderBy + ThenBy   : 00:00:00.0128862
  Sort(Comparison<T>): 00:00:00.0000396
  OrderBy + ThenBy   : 00:00:00.0000497
  Sort(Comparison<T>): 00:00:00.0000282
  OrderBy + ThenBy   : 00:00:00.0000357
10,000
  Sort(Comparison<T>): 00:00:00.0039588
  OrderBy + ThenBy   : 00:00:00.0056537
  Sort(Comparison<T>): 00:00:00.0045002
  OrderBy + ThenBy   : 00:00:00.0042474
  Sort(Comparison<T>): 00:00:00.0038242
  OrderBy + ThenBy   : 00:00:00.0048581
1,000,000
  Sort(Comparison<T>): 00:00:01.0339300
  OrderBy + ThenBy   : 00:00:01.4343420
  Sort(Comparison<T>): 00:00:01.0314824
  OrderBy + ThenBy   : 00:00:01.2782487
  Sort(Comparison<T>): 00:00:01.0515235
  OrderBy + ThenBy   : 00:00:01.5493575
実行結果 (Ubuntu 11.10 + Mono 2.10.6)
Unix 3.0.0.14
4.0.30319.1
100
  Sort(Comparison<T>): 00:00:00.0013989
  OrderBy + ThenBy   : 00:00:00.0164684
  Sort(Comparison<T>): 00:00:00.0000365
  OrderBy + ThenBy   : 00:00:00.0000487
  Sort(Comparison<T>): 00:00:00.0000362
  OrderBy + ThenBy   : 00:00:00.0000495
10,000
  Sort(Comparison<T>): 00:00:00.0070140
  OrderBy + ThenBy   : 00:00:00.0058386
  Sort(Comparison<T>): 00:00:00.0063343
  OrderBy + ThenBy   : 00:00:00.0051259
  Sort(Comparison<T>): 00:00:00.0065034
  OrderBy + ThenBy   : 00:00:00.0058673
1,000,000
  Sort(Comparison<T>): 00:00:01.3199098
  OrderBy + ThenBy   : 00:00:01.1463424
  Sort(Comparison<T>): 00:00:01.2777875
  OrderBy + ThenBy   : 00:00:01.1191267
  Sort(Comparison<T>): 00:00:01.2825583
  OrderBy + ThenBy   : 00:00:01.1213952

単一のキーでソートした場合の結果については、基本型のソートと昇順・降順でのソート §.パフォーマンスの比較を参照してください。