無差別に技術をついばむ鳥

#include 
using namespace std;

//保持するデータの最大数
static const int MAX = 10;

//マージソート
class SearchMan {
private:

//要素を交換する
static void Exchange( int values[], int destination, int source ) {
    int tmp = values[ destination ];
    values[ destination ] = values[ source ];
    values[ source ] = tmp;
}

//指定した範囲のソースをもとに、2個に分割を行う。
static void Divide( int* source, int start, int end, 
    int*& leftArray, int*& rightArray ) {

    //分割後のサイズを求める
    int length = start + end;
    int leftSize = length / 2;
    int rightSize = length - leftSize;

    //分割する
    leftArray = new int[ leftSize ];
    rightArray = new int[ rightSize ];

    //元の値をコピーする
    for ( int i = 0; i < leftSize; i++ ) 
	leftArray[ i ] = source[ i ];
    for ( int i = 0; i < rightSize; i++ ) 
	rightArray[ i ] = source[ i + leftSize ];
}
	
//2つの配列をソートして一つの場所へ出力する
static void Merge( int* leftArray, int leftSize,
	int* rightArray, int rightSize, int*& outArray ) {
		
    //各種変数を準備
    int leftIndex = 0;
    int rightIndex = 0;
    int outIndex = 0;
    outArray = new int[ leftSize + rightSize ];

    //左右を比較しながら出力
    while( leftIndex < leftSize && rightIndex < rightSize ) {
	//小さいほうを出力
	if ( leftArray[ leftIndex ] <= rightArray[ rightIndex ] ) {
		outArray[ outIndex ] = leftArray[ leftIndex ];
		leftIndex++;
	} else {
		outArray[ outIndex ] = rightArray[ rightIndex ] ;
		rightIndex++;
	}
	outIndex++;
    }

    //残りを出力
    if( leftIndex < leftSize ) {
	for( int i = leftIndex; i < leftSize; i++ ) {
		outArray[ outIndex ] = leftArray[ i ];
		outIndex++;
	}
    } else {
	for( int i = rightIndex; i < rightSize; i++ ) {
		outArray[ outIndex ] = rightArray[ i ];
		outIndex++;
	}
    }
    return;
}

public :

static void MergeSort( int*& source, int start, int end ) {

    //長さが1ならばこれ以上分割できないので何もしない
    int length = start + end;
    if ( length == 1 ) return;

    //長さが2の場合は交換だけして終わる
    if ( length == 2 ) {
	if ( source[ 0 ] > source[ 1 ] ) 
		Exchange( source, 0, 1 );
	return;
    }

    //半分に分割する
    int* leftArray = 0;
    int* rightArray = 0;
    int leftSize = length / 2;
    int rightSize = length - leftSize;
    Divide( source, start, end, leftArray, rightArray );

    //分割後の配列に対してマージソートを行う
    MergeSort(leftArray, 0, leftSize);
    MergeSort(rightArray, 0, rightSize );

    //ソート後の2つの配列を融合する
    int* outArray = 0;
    Merge( leftArray, leftSize, rightArray, rightSize, outArray );

    //結果を反映する
    source = outArray;

    //後始末
    delete leftArray;
    delete rightArray;
}

};

int main(void)
{
    int values[MAX] = { 9,3,5,6,2,8,7,0,1,4 };
    int* result = (int*)values;

    //整理前のデータを確認
    cout << "整列前のデータを表示します。" << endl;
    for(int i = 0; i < MAX; i++) cout << values[i] << '\t';
    cout << endl;

    //ソートする
    SearchMan::MergeSort( result, 0, MAX );

    //整理後のデータを確認
    cout << "整列後のデータを表示します。" << endl;
    for(int i = 0; i < MAX; i++) cout << result[i] << '\t';
    cout << endl;
    return 0;
}