C++でのマージソートの実現方法について

質問

C++でのマージソートの実現方法について、以下のコードを書いたのですが、どうしてもうまくソートできませんでした。

marge関数がおかしいと思うのですが、自分で確かめてみても、どこがおかしいのか分かりませんでした。
どなたか、どうすればソートされた結果がメイン関数で表示されるようにできるのか教えていただけないでしょうか？

#include <iostream>
#include <vector>
using namespace std;

class Array {
private:
vector<int> array;
public:
void insert( int value ){ array.push_back( value ); }
int getSize( ){ return (int)array.size( ); }
void marge_sort( ){ marge_sort( 0, (int)array.size( ) - 1 ); }
void marge_sort( int left, int right );
void marge( int left, int middle, int right );
void print( );
};

// マージソートにより配列の添字 left ～ right の部分を整列する関数
void Array::marge_sort( int left, int right ){

if( left >= right ) {
return;
}

int middle = (left + right) / 2; //中央の添字を求める

marge_sort( left, middle ); //左の要素が全てバラバラになるまで
marge_sort( middle + 1 , right ); //右の要素が全てバラバラになるまで

marge( left, middle, right ); //バラバラの要素をソートして併合

}

// 個別にソートされた2つの配列（添字 left ～ middle と添字 middle+1 ～ right）を作業用配列を使ってマージする関数
void Array::marge( int left, int middle, int right ) {

int num=right-left;
int *tmp=new int[num];

int t=0,l=left,r=middle;

while(l<middle&&r<right){

if(array[l]<=array[r]){
tmp[t++]=array[l++];
}
else {
tmp[t++]=array[r++];
}
}

while(l<middle){
tmp[t++]=array[l++];
}
while(r<right){
tmp[t++]=array[r++];
}

for(int i=0;i<num;i++){
array[left+i]=tmp[i];
}

delete tmp;
}

// 配列の内容を表示する関数
void Array::print( ) {
for ( int i = 0; i < (int)array.size( ); i++ ) {
cout << array[i] << " ";
}
cout << endl;
}

int main( ) {

Array a1;

a1.insert( 56 );
a1.insert( 34 );
a1.insert( 57 );
a1.insert( 64 );
a1.insert( 3 );
a1.insert( 87 );
a1.insert( 85 );
a1.insert( 37 );
a1.insert( 21 );
a1.insert( 4 );
a1.insert( 68 );
a1.insert( 62 );
a1.insert( 42 );
a1.insert( 55 );
a1.insert( 63 );
a1.insert( 95 );
a1.insert( 7 );
a1.insert( 32 );
a1.insert( 78 );
a1.insert( 11 );

cout << "要素数: " << a1.getSize( ) << endl;
cout << "ソート前: ";
a1.print( );

a1.marge_sort(); // ここで，ソートを行う関数を呼び出す

cout << "ソート後: ";
a1.print( );

return 0;
}

// 実行結果

要素数: 20
ソート前: 56 34 57 64 3 87 85 37 21 4 68 62 42 55 63 95 7 32 78 11
ソート後: 3 4 34 37 21 42 55 56 57 62 63 7 32 64 68 78 85 87 95 11

↑のソート後の表示が、昇順にソートされるようにしたいのです。

回答No.1

f272 · ベストアンサー

> int num=right-left;

個数はright-left+1だよね。

> int t=0,l=left,r=middle;

rはmiddle+1から始まるよね。

> while(l<middle&&r<right){
> while(l<middle){
> while(r<right){

l=middleでもr=rightでも実行させるべきだよね。

お礼

簡潔かつ適格にご指摘してくださり、ありがとうございます。
確かに、悩んでいた部分を解消することができました。
重ねて感謝申し上げます。