C言語のアルゴリズム、マージソートについて質問です。

質問

C言語のアルゴリズム、マージソートについて質問です。
例えば下のプログラム
#include <stdio.h>

void merge(int first, int last, int *data, int *work);

int main(void)
{
int data[9] = {1,8,3,6,5,4,7,2};
int work[9];
int i;

merge(0,8,data,work);

for(i = 0;i < 9;i++) printf("%d",data[i]);

return 0;
}

void merge(int first, int last, int *data, int *work)
{
int middle, mae, ato, i;

if (first == last)
{
return;
}

middle = (first + last) / 2;

merge(first, middle, data, work);

merge(middle + 1, last, data, work);

i = first;
mae = first;
ato = middle + 1;

while (mae <= middle && ato <= last)
{
if (data[mae] <= data[ato])
{
work[i] = data[mae];
i++;
mae++;
}
else
{
work[i] = data[ato];
i++;
ato++;
}
}

while (mae <= middle)
{
work[i] = data[mae];
i++;
mae++;
}

while (ato <= last)
{
work[i] = data[ato];
i++;
ato++;
}

for (i = first; i <= last; i++)
{
data[i] = work[i];
}

}

まずfirst=0,last=8でmerge関数に入り関数内８行目でmiddle=4となり、
１０行目でfirst=0,last=4でmergeに入り同じく８行目でmiddle=2となり、
同じく１０行目でfirst=0,last=2でmergeに入り同じく８行目でmiddle=1となり、
同じく１０行目でfirst=0,last=1でmergeに入り同じく８行目でmiddle=0となり、
同じく１０行目でfirst=0,last=0でmergeに入り３行目のifでreturnします。
そして前回のfirst=0,last=1,middle=0のmerge１０行目に戻り,
１２行目でfirst=1,last=1でmergeに入り３行目のifでreturnし、
１２行目以下の作業をします。
そのまま一番下までいったあとはどうなるのでしょうか？
また上で書いた手順もあっている自信はあまりないので
ご指摘お願いします。

回答No.5

和泉 博（@hiroshi09s）

#3です。まず、字数の関係で載せられなかった実行結果を示しておきます。

----- 実行結果 -----
first=0 last= 7 middle= 3
first=0 last= 3 middle= 1
first=0 last= 1 middle= 0
first=0 last= 0 ...return
first=1 last= 1 ...return
merging 0 1 (case middle 0 [0 - 1])
first=2 last= 3 middle= 2
first=2 last= 2 ...return
first=3 last= 3 ...return
merging 2 3 (case middle 2 [2 - 3])
merging 0 2 (case middle 1 [0 - 3])
first=4 last= 7 middle= 5
first=4 last= 5 middle= 4
first=4 last= 4 ...return
first=5 last= 5 ...return
merging 4 5 (case middle 4 [4 - 5])
first=6 last= 7 middle= 6
first=6 last= 6 ...return
first=7 last= 7 ...return
merging 6 7 (case middle 6 [6 - 7])
merging 4 6 (case middle 5 [4 - 7])
merging 0 4 (case middle 3 [0 - 7])
Result:
1 2 3 4 5 6 7 8

答えは、肝心の境界値があなたの質問と異なっています。
答えは
http://www.codereading.com/algo_and_ds/algo/merge_sort.html
の通り、
first=1,last=1でdata[0-1]間のmergeに入り３行目のifでreturnし、
１２行目以下の作業、すなわち mergingを行います。
そのまま一番下にいったあとは、次の配列data[2-3]について同じ操作を繰り返します。

回答No.4

asuncion

＞インデントをつけられてはいかがでしょうか

ここの掲示板は、インデントを無視してしまうのです。
残念なことに。

回答No.3

和泉 博（@hiroshi09s）

データ数と出力 for() の内容があっていませんが、プログラム間違ってません？
以下のプログラムを実行してみると、再帰ゆえ、あなたが答えるほど内容は簡単ではないようです。
http://www.codereading.com/algo_and_ds/algo/merge_sort.html

#include <stdio.h>
#define KOSU 8

void merge(int, int, int *, int *);

int main(void)
{
int data[KOSU] = {1,8,3,6,5,4,7,2};
int work[KOSU];
int i;

merge(0,KOSU-1,data,work);

printf("Result:\n");
for(i = 0; i < KOSU; i++) printf("%d ",data[i]);
printf("\n");

return 0;
}

void merge(int first, int last, int *data, int *work)
{
int middle, mae, ato, i;

printf("\tfirst=%d \tlast= %d ", first, last);
if (first == last) {
printf("\t...return\n");
return;
}

middle = (first + last) / 2;
printf("\tmiddle= %d\n", middle);
merge(first, middle, data, work);
merge(middle + 1, last, data, work);

i = mae = first;
ato = middle + 1;
printf("\tmerging %d %d (case middle %d [%d - %d])\n",
mae, ato, middle, first, last);
while (mae <= middle && ato <= last) {
if (data[mae] <= data[ato]) work[i++] = data[mae++];
else work[i++] = data[ato++];
}
while (mae <= middle) work[i++] = data[mae++];
while (ato <= last) work[i++] = data[ato++];

for (i = first; i <= last; i++) data[i] = work[i];
}

回答No.2

ohtawa

どうなるでしょうかって
実行させてみればよいではありませんか

それから　ソースがよみづらいです
インデントをつけられてはいかがでしょうか

途中の過程を追いかけたかったら
デバッグツールを使うのも一法かと

回答No.1

Tacosan

「一番下」というのが「関数の終わりの }」のことであれば, そこまでいったら自動的に return します.