マージ・ソート : 巨大データのソート法

C#, VB.NET, C++/CLI で学ぶアルゴリズム

　これで準備完了です。C#コードを示します（VB.NET, C++/CLIは長くなるので割愛、添付プロジェクトを参照してください）。

C# マージ・ソート 全ソース

using System;
using System.IO;
using System.Collections.Generic;

namespace MergeSortOnFile_csharp {

  interface IQueReader<T> where T : IComparable<T> {
    bool Available { get; } // 入力が空ではない
    T    Current { get; }   // 現在の値
    void ReadNext();        // 次を読め
    bool EndOfRun { get; }  // 連の切れ目か?
  }

  interface IQueWriter<T> {
    void Write(T val); // valを書け
  }

  static class QueExtention {
    // readerからwriterへ一つコピーする
    public static void CopyTo<T>(this IQueReader<T> reader,
      IQueWriter<T> writer) where T : IComparable<T> {
      writer.Write(reader.Current); // readerの現在値をwriterに書いて
      reader.ReadNext(); // 次を読んでおく
    }
    // 連の切れ目に達するまでreaderからwriterに転写する
    public static void CopyRunTo<T>(this IQueReader<T> reader,
      IQueWriter<T> writer) where T : IComparable<T> {
      do {
        reader.CopyTo(writer);
      } while (!reader.EndOfRun);
    }
  }

  // 文字列版QueReader : IQueReader<string> の実装
  class StringQueReader : IQueReader<string> {
    private TextReader reader_;
    private string last_ = null;
    public StringQueReader(TextReader reader) {
      reader_ = reader;
      ReadNext();
    }
    public bool Available { get { return Current != null; }}
    public string Current { get; private set; }
    public void ReadNext() {
      last_ = Current; Current = reader_.ReadLine();}
    public void Close() { reader_.Close(); }
    public bool EndOfRun {
      get { return !Available || Current.CompareTo(last_) < 0; }}
  }

  // 文字列版QueWriter : IQueWrite<string>の実装
  class StringQueWriter : IQueWriter<string> {
    private TextWriter writer_;
    public StringQueWriter(TextWriter writer) { writer_ = writer; }
    public void Write(string val) { writer_.WriteLine(val);}
    public void Close() { writer_.Close(); }
  }

  class Program {

    /* -------------------- *
     * マージ・ソートの本体
     * -------------------- */
    public static void merge_sort(string in_path, string out_path) {
      {
        /*
         * ちょっとした高速化:
         * ある程度ソートしておくことによって連を減らし、
         * 分割/併合回数を減らす
         */
        StreamReader reader = new StreamReader(in_path);
        StreamWriter writer = new StreamWriter(out_path);
        string line;
        List<string> strList = new List<string>();
        int readLength = 0;
        do {
          // 入力をList<string>に貯め込み
          line = reader.ReadLine();
          if ( line != null ) {
            readLength += line.Length;
            strList.Add(line);
          }
          // 適当な量貯まったら
          if ( line == null || readLength > 1000000 ) {
            // ソートして
            strList.Sort();
            // 書き出す
            foreach ( string item in strList ) {
              writer.WriteLine(item);
            }
            readLength = 0;
            strList.Clear();
          }
        } while ( line != null );
        reader.Close();
        writer.Close();
      }

      /*
       * マージ・ソートはここから。
       */
      int RunCount;　// 併合後の連の数
      do {
        /*
         * 分割フェーズ
         */
        StringQueReader reader =
          new StringQueReader(new StreamReader(out_path));
        StringQueWriter writer1 =
          new StringQueWriter(new StreamWriter("tmp1.txt"));
        StringQueWriter writer2 =
          new StringQueWriter(new StreamWriter("tmp2.txt"));
        for (;;) {
          if ( reader.Available ) reader.CopyRunTo(writer1);
            else break; // 連をreaderからwriter1へ
          if ( reader.Available ) reader.CopyRunTo(writer2);
            else break; // 連をreaderからwriter2へ
        }
        reader.Close();
        writer1.Close();
        writer2.Close();

        /*
         * 併合フェーズ
         */
        StringQueReader reader1 =
          new StringQueReader(new StreamReader("tmp1.txt"));
        StringQueReader reader2 =
          new StringQueReader(new StreamReader("tmp2.txt"));
        StringQueWriter writer =
          new StringQueWriter(new StreamWriter(out_path));
        RunCount = 0;
        // reader1,2共に空でない間
        while ( reader1.Available && reader2.Available ) {
          for (;;) {
            // 両者の大小に応じて
            if ( reader1.Current.CompareTo(reader2.Current) < 0 ) {
              reader1.CopyTo(writer); // reader1からwriterへ
              if ( reader1.EndOfRun ) { // 連の切れ目に達したら
                reader2.CopyRunTo(writer); // reader2の連をwriterへ
                break;
              }
            } else {
              reader2.CopyTo(writer);　// reader2からwriterへ
              if ( reader2.EndOfRun ) { // 連の切れ目に達したら
                reader1.CopyRunTo(writer); // reader1の連をwriterへ
                break;
              }
            }
          }
          ++RunCount;
        }
        while ( reader1.Available ) { // reader1が空になるまで
          reader1.CopyRunTo(writer); // 連をwriterへ
          ++RunCount;
        }
        reader1.Close();
        while ( reader2.Available ) { // reader2が空になるまで
          reader2.CopyRunTo(writer); // 連をwriterへ
          ++RunCount;
        }
        reader2.Close();
        writer.Close();
      } while ( RunCount != 1 ); // 併合後の連の数が1であるなら完了
      File.Delete("tmp1.txt");
      File.Delete("tmp2.txt");
    }

    public static void Main() {
      merge_sort("input.txt","result.txt");
    }

  }
}