回答編集履歴

1 コードの追加

kazuma-s

kazuma-s score 5132

2019/07/17 09:14  投稿

> これらを部分的に修正していきたいと思っておりますので、
元の質問のコードにはまだ誰も指摘していない間違いがあるのですが、
もう解決済みですか?
質問を編集して、解決したコードを追記してください。
2つ目の Y[i++] = Y2[j++]; は Y[i++] = Y1[j++]; でしょう。
> プログラム全体の方針等は目を瞑っていただければと思います。
目を瞑りたくないなあ。
再帰呼出しで、ローカルに大きな配列を確保し続けると、
スタックオーバーフローが起きやすくなりますよ。
スタックオーバーフローが起きやすくなりますよ。
### 追記
最初に1回 msort の中で必要な領域を確保しておけば、
再帰呼出しの merge_sort ではそれを使うだけのコードを書いてみました。
```C
#include <stdio.h>  // printf, putchar
#include <stdlib.h> // malloc, free
#define N 8
void show(int x[], int n)
{
   for (int i = 0; i < n; i++) printf(" %d", x[i]);
   putchar('\n');
}
void merge(int x[], int m, int y[], int n, int t[])
{
   int i = 0, j = 0, k = 0;
   while (j < m && k < n) t[i++] = (x[j] < y[k]) ? x[j++] : y[k++];
   while (j < m) t[i++] = x[j++];
   while (k < n) t[i++] = y[k++];
}
void merge_sort(int x[], int n, int t[])
{
   if (n < 2) return;
   int n1 = n / 2, n2 = n - n1;
   merge_sort(x, n1, t);
   merge_sort(x + n1, n2, t);
   merge(x, n1, x + n1, n2, t);
   for (int i = 0; i < n; i++) x[i] = t[i];
}
void msort(int x[], int n, int y[])
{
   int *t = malloc(sizeof(int) * n * 2);
   if (!t) { puts("out of memory"); return; }
   for (int i = 0; i < n; i++) t[i] = x[i];
   merge_sort(t, n, t + n);
   for (int i = 0; i < n; i++) y[i] = t[i];
   free(t);
}
int main()
{
   int x[N] = { 18, 37, 21, 14, 7, 12, 19, 6 }, y[N];
   show(x, N);
   msort(x, N, y);
   show(y, N);
}
```

思考するエンジニアのためのQ&Aサイト「teratail」について詳しく知る