再帰型マージソート

Person.java

public class Person implements Comparable {
    private int id;
    private String name;

    public Person( int id, String name ) {
        this.id = id;
        this.name = name;
    }

    public Person() {
        this.id = 0;
        this.name = "";
    }

    public int getId() { return id; };
    public String getName() { return name; };

    @Override
    public int compareTo( Object obj ) {
        return this.name.compareTo( ((Person)obj).name );
    };

    @Override
    public boolean equals( Object obj ) {
        if ( this.getId() == ((Person)obj).getId() &&
             this.getName() == ((Person)obj).getName() ) {
            return true;
        } else {
            return false;
        }
    }
};

Sort.java

import java.util.ArrayList;
import java.util.Collections;

public class Sort <T extends Comparable> {
    private ArrayList<T> array;
    private ArrayList<T> buf;

    // ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
    private void merge( int index_b, int index_c, int index_e ) {
        // 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
        if ( index_b + 1 == index_e ) {
            if ( array.get(index_e).compareTo(array.get(index_b)) < 0 ) {
                T tmp = array.get(index_e);
                array.set(index_e, array.get(index_b));
                array.set(index_b, tmp);
            }
            return;
        }

        // index_1とindex_2を動かしながら，小さい方を順次index_bufへ書き込む
        int index_1 = index_b;
        int index_2 = index_c + 1;
        int index_buf = index_b;

        while ( true ) {
            if ( array.get(index_1).compareTo(array.get(index_2)) < 0 ) {
                buf.set(index_buf++, array.get(index_1));
                // index_1が最後まで到達したらindex_2側を順番に見て終了
                if ( index_1++ == index_c ) {
                    while ( index_2 <= index_e ) {
                        buf.set(index_buf++, array.get(index_2++));
                    }
                    break;
                }
            } else {
                buf.set(index_buf++, array.get(index_2));
                // index_2が最後まで到達したらindex_1側を順番に見て終了
                if ( index_2++ == index_e ) {
                    while ( index_1 <= index_c ) {
                        buf.set(index_buf++, array.get(index_1++));
                }
                    break;
                }
            }
        }

        // バッファから元配列へコピー
        for ( int i = index_b; i <= index_e; i++ ) {
            array.set(i, buf.get(i));
        }

        return;
    };

    // 再帰的に呼び出す関数
    private void merge_sort( int index_b, int index_e ) {
        int index_c = ( index_b + index_e ) / 2;

        // 左側をソート
        if ( index_b != index_c )
            merge_sort( index_b, index_c );

        // 右側をソート
        if ( (index_c + 1) != index_e )
            merge_sort( index_c + 1, index_e );

        // 左と右をマージ
        merge( index_b, index_c, index_e );

        return;
    };

    // mainから呼ぶソート関数
    public void merge_sort( ArrayList<T> vec ) {
        // ソート対象の配列
        array = vec;

        // マージ中のソート結果を一時的に記憶するバッファ
        buf = new ArrayList<T>( Collections.nCopies( vec.size(), null ) );

        // マージソート
        merge_sort( 0, vec.size() - 1 );
    };
};

sort_test.java

import java.util.ArrayList;
import java.util.Collections;
import java.lang.management.ThreadMXBean;
import java.lang.management.ManagementFactory;
import java.util.Scanner;

public class sort_test {
    public static void main(String[] args) {
        // 時間測定のためのオブジェクト・変数
        ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();
        long startTime, endTime;

        // 標準入力からデータを読み込み
        ArrayList<Person> arrayPeople = new ArrayList<Person>();
        Scanner scanner = new Scanner(System.in);
        int id;
        String name;

        startTime = threadMXBean.getCurrentThreadCpuTime();

        while ( true ) {
            try {
                id = scanner.nextInt();
                name = scanner.next();
                arrayPeople.add( new Person( id, name ) );
            } catch ( Exception e ) {
                break;
            }
        }

        endTime = threadMXBean.getCurrentThreadCpuTime();
        System.out.println( "reading : " + ( (double)( endTime - startTime ) / 1000000000.0 ) );

        // 読み込んだデータをソート
        Sort<Person> sort = new Sort<Person>();

        startTime = threadMXBean.getCurrentThreadCpuTime();

        sort.merge_sort( arrayPeople );
        // Collections.sort( arrayPeople );

        endTime = threadMXBean.getCurrentThreadCpuTime();
        System.out.println( "sorting : " + ( (double)( endTime - startTime ) / 1000000000.0 ) );

        // ソート済み確認
        for ( int i = 1; i < arrayPeople.size(); i++ ) {
            if ( arrayPeople.get(i).compareTo( arrayPeople.get(i-1) ) < 0 ) {
                System.out.println( "ERROR" );
            }
        }
    };
};