その中で一番簡単なマージソートというアルゴリズムを示す．
// 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 +" 回です");
}
}
これを 1013.html に対して適応してみると比較回数は 277回となった．59行
程度の小さいプログラムを相手にしていたので，4倍程度のスピードアップに
終わっているが大きなプログラムを相手にすると更に変わるはずである．