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し、
１２行目以下の作業をします。
そのまま一番下までいったあとはどうなるのでしょうか？
また上で書いた手順もあっている自信はあまりないので
ご指摘お願いします。
お礼
ありがとうございます