効率の良いソートアルゴリズム

その中で一番簡単なマージソートというアルゴリズムを示す．

 // BufferedReaderなどを使うので，java.io.*を import する．
import java.io.*;
 // Vectorを使うので java.util.* を importする．
import java.util.*;

class SortTest3 {
   // 比較回数を記録するための変数
  static int compareCount=0;
   // s1とs2を比較してs1が辞書式順序で小さいときは負，等しいときは0，大きいときは正の整数を返す
  static int compare(String s1, String s2){
    compareCount++;
    return s1.compareTo(s2);
  }
  // ソート済みの配列 src1とsrc2を合わせて，ソート済みの配列を作る
  static String[] merge(String[] src1, String[] src2){
    int len1=src1.length, len2=src2.length;
     // 合わせた要素を入れる文字列を作る
    String[] dst=new String[len1+len2];
     // 文字列 src1, src2, dstの何番目に注目しているかを示すインデックス(添字)
    int i1=0,i2=0,i3=0;
    for(;;){
      // src1とsrc2から先頭の要素を1つ取る．
      // src1の先頭の方が小さい時は，
      if(compare(src1[i1],src2[i2])<0){
      // src1から1つ要素を取り，dstに加える
      // dst[i3]=src1[i1]; i3++; i1++; と同じ
	dst[i3++]=src1[i1++];
	// src1の要素が残っていない時は，src2の残り部分を dstにコピーして終了する
	if(i1>=len1) {
	  System.arraycopy(src2,i2,dst,i3,len2-i2);
	  break;
	}
      }
      // src2の要素の方が小さいときは
      else{
        // src2から1つ要素を取り，dstに加える
        // dst[i3]=src2[i2]; i3++; i2++; と同じ
	dst[i3++]=src2[i2++];
	// src2の要素が残っていない時は，src1の残り部分を dstにコピーして終了する
	if(i2>=len2) {
	  System.arraycopy(src1,i1,dst,i3,len1-i1);
	  break;
	}
      }
    }
    return dst;
  }
  // linesの内容をソートする
  static void sort(String[] lines){
    int i,j,len=lines.length;
    // 要素数が0，1の場合はソート済みなのでそのまま返す
    if(len<2) return;
    // linesの前の半分，後の半分の入った配列 s1, s2を作る
    int len1=len/2;
    int len2=len-len1;
    String[] s1=new String[len1],s2=new String[len2];
    System.arraycopy(lines,0,s1,0,len1);
    System.arraycopy(lines,len1,s2,0,len2);
    // s1, s2をそれぞれソートする
    sort(s1);
    sort(s2);
    // ソート済みのs1, s2を合わせてソート済みの配列を作る
    String[] sorted=merge(s1,s2);
    // linesにコピーする
    System.arraycopy(sorted,0,lines,0,len);
  }
  //  IOExceptionを catchしていないので,throws IOExceptionをつける．
  public static void main(String args[]) throws IOException{
    // ファイル名と思って BufferedReader
    BufferedReader is=new BufferedReader(new FileReader(args[0]));
    // 何行になるかわからないので,Vectorで記憶しておく
    Vector v=new Vector();
    String s;
    // 1行読み込んでファイルの終端に到達しない間
    while((s=is.readLine())!=null){
      // Vectorの最後に要素を加える
      v.addElement(s);
    }
    // 入力ストリームを閉じる
    is.close();
    // Vectorから配列に変換するために,領域を確保する
    String[] lines=new String[v.size()];
    // Vectorから配列に変換する．
    v.copyInto(lines);
    // ソートする
    sort(lines);
    // ソートした結果を出力する．
    for(int i=0;i< lines.length;i++)
      System.out.println(lines[i]);
    System.err.println("比較回数は "+ compareCount +" 回です");
  }
}