マージソートについて

質問

void mergesort (int n, int x[])
{
int i,j,k,m;
if(n<=1)
return;
m=n/2; ここで分割するのは分かるのですが

mergesort(m,x);　　　　　　再帰させてなんでこの式でブロックを
mergesort(n-m,x+m);　　　　前半と後半に分けれるのか、分かりま
　　　　　　　　　　　　　　　　　せん。だれか教えてください！（＞＜）

回答No.1

noname#77845 · ベストアンサー

この関数自体が、配列の要素数を知らないのでスタート位置とソートする個数を教えてやっているのです。

簡単な例でトレースしてみましょう。
最初に
x[0],x[1],x[2],…,x[10],x[11]
という配列があったとします。
関数を呼び出すときは
mergsort(12,x);
のようになるはずです。
呼び出された側はx[0]から12個に処理をします。
m=n/2;
でmが6になりますよね？
そこで、
mergsort(m,x);
を考えると、x[0]から6個(x[0],x[1],x[2],x[3],x[4],x[5])処理をすることになります。
また、
mergsort(n-m,x+m);
を考えると、n-mは6、x+mはx[6]を表しますからx[6]から6個(x[6],x[7],x[8],x[9],x[10],x[11])処理することになります。

判りますか？

因みに、n-mとしているのは割り切れなかったときのことを考えての事です。
最初にnが11だったら、
m=n/2
は、5になりますから前半部分はx[0]から5個(x[0],x[1],x[2],x[3],x[4])、後半部分は11-5=6でx[5]から6個(x[5],x[6],x[7],x[8],x[9],x[10])処理することになります。

補足

プログラムを追うため少しプログラムを変えてみました。

void mergesort(int n,int x[])
{
int m,s;
for(s=0;s<n;s++)
{
printf("%d\n",x[s]);
}
puts("小休止");

if(n<=1)

return;
m=n/2;
mergesort(n-m,x+m);

}
これの実行結果は
12345678910
小休止678910
小休止8910
小休止910
小休止10
小休止
でした。
これはx+mは配列の中を（もしmが５であったら、x[5]以降のみに）変えるということと解釈してよいのでしょうか？

回答No.2

noname#77845

＃１です。

配列を変えるのではなく、x[5]から始まる配列を1つの配列と認識しているんだと思います。
受け取った側は何番から始まるかは関係ないので（エラーにならない限り）、送る側で「次はここからここまでをよろしく～」と渡しているだけですね。