再帰型マージソート（ポインタ配列用）

sort_test_ptr.cpp

#include <vector>
#include <string>
#include <iostream>
#include <ctime>

class Person {
private:
    int id;
    std::string name;

public:
    Person( int id, const char* name ) {
        this->id = id;
        this->name = name;
    }

    Person() {
        this->id = 0;
        this->name = "";
    }

    int get_id() { return id; };
    std::string get_name() { return name; };

    bool operator< ( Person &p2 ) {
        return this->name < p2.name;
    };

    Person &operator=( const Person &p ) {
        this->id = p.id;
        this->name = p.name;
        return *this;
    }

};

template<class T> class Sort {
    T *buf;
    std::vector<T> *array;

public:
    Sort() {
    };

private:
    // ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
    void merge( int index_b, int index_c, int index_e ) {
        // 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
        if ( index_b + 1 == index_e ) {
            if ( *(*array)[index_e] < *(*array)[index_b] ) {
                auto tmp = (*array)[index_e];
                (*array)[index_e] = (*array)[index_b];
                (*array)[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)[index_1] < *(*array)[index_2] ) {
                buf[index_buf++] = (*array)[index_1];
                // index_1が最後まで到達したらindex_2側を順番に見て終了
                if ( index_1++ == index_c ) {
                    while ( index_2 <= index_e ) {
                        buf[index_buf++] = (*array)[index_2++];
                    }
                    break;
                }
            } else {
                buf[index_buf++] = (*array)[index_2];
                // index_2が最後まで到達したらindex_1側を順番に見て終了
                if ( index_2++ == index_e ) {
                    while ( index_1 <= index_c ) {
                        buf[index_buf++] = (*array)[index_1++];
                }
                    break;
                }
            }
        }

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

        return;
    };

    // 再帰的に呼び出す関数
    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;
    };

public:
    // mainから呼ぶソート関数
    // ポインタの配列を渡すことを前提としている
    void merge_sort( std::vector<T> *vec ) {
        // ソート対象の配列
        this->array = vec;

        // マージ中のソート結果を一時的に記憶するバッファ
        this->buf = new T[ vec->size() ];

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

        delete [] buf;
    };

};

int main(int argc, char *argv[]) {
    // 時間測定のための変数
    struct timespec tp_start, tp_end;

    // 標準入力からデータを読み込み
    std::vector<Person*> vec_people;
    int id;
    std::string name;

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_start);

    while ( std::cin >> id && std::cin >> name ) {
        vec_people.push_back( new Person( id, name.c_str() ) );
    }

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_end);
    std::cout << "reading : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;

    // 読み込んだデータをソート
    Sort<Person*> sort;

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_start);

    sort.merge_sort( &vec_people );

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_end);
    std::cout << "sorting : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;

    // ソート済み確認
    for ( int i = 1; i < vec_people.size(); i++ ) {
        if ( *(vec_people[i]) < *(vec_people[i-1]) ) {
            std::cerr << "ERROR" << std::endl;
        }
    }

    for ( auto p : vec_people ) {
        delete p;
    }

    return 0;
}