マージソートの入力がある数を越えると作動しなくなる。

Question

要素の数を事前に指定し、1~20のいずれかで作られた数字列をマージソートするプログラムなのですが、要素数Nを173643以上の数とすると実行されず、コンパイラがフリーズしてしまいます。
環境はVisual Studio CodeとMinGWなのですが、何か対処法はありますでしょうか。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 173642

void Merge(int *S,int left,int right);
void MergeSort(int *S,int left,int right);

int main(void)
{
    int i,S[N];
    long cpu_time;

    srand((unsigned)time(NULL));
    for(i=0; i<N; ++i){
        S[i]=rand()%20+1;  //1~20までの乱数生成
    }

    
    for(i=0; i<N; ++i){
        printf("%d ",S[i]);
    }

    printf("\n");

    cpu_time=clock();

    MergeSort(S,0,N-1);

    for(i=0; i<N; ++i){
        printf("%d ",S[i]);
    }

    printf("\nN=%d,CPU Time: %.4f [sec]\n",N,(double)(clock()-cpu_time)/CLOCKS_PER_SEC);

    return 0;
}

void MergeSort(int *S,int left,int right)
{
    int mid;

    mid=(left+right)/2;

    if(left<right){  //配列の要素数が2以上のとき
        MergeSort(S,left,mid);
        MergeSort(S,mid+1,right);
        Merge(S,left,right);
    }
}

void Merge(int *S,int left,int right)
{
    int i,mid,size_L,size_R;
    int j=1,k=1; 
    int L[N],R[N];

    mid=(left+right)/2;
    size_L=mid-left+1;  //左側配列の大きさ
    size_R=right-mid;   //右側配列の大きさ

    for(i=0; i<size_L; ++i){
        L[i]=S[left+i];
    }

    for(i=0; i<size_R; ++i){
        R[i]=S[mid+i+1];
    }

    for(i=1; i<=size_L+size_R; ++i){
        if(j>size_L){
            S[left+i-1]=R[k-1];
            ++k;
        }else if(k>size_R){
            S[left+i-1]=L[j-1];
            ++j;            
        }else if(L[j-1]<R[k-1]){
            S[left+i-1]=L[j-1];
            ++j;
        }else{
            S[left+i-1]=R[k-1];
            ++k;
        }
    }
}

コンパイラの表示は以下のようになり、次の入力を促されてしまいます。

…
N=173642,CPU Time: 18.6740 [sec] //N=173642の場合実行可能
PS C:\programming> .\a.exe 　 //N=173643にすると実行されない

PS C:\programming>

Answer 1

Merge内の配列LとRをmallocで動的に確保することで解決できました。
具体的に分析して対処法を上げて下さったkazuma-sさんをベストアンサーに選ばせて頂きます。

Answer 2

sizeof(int) が 4 とすれば、
main の中の int S[N]; について、 sizeof(S) = 173642 x 4 = 694568バイト。
Merge の中の sizeof(L) と sizeof(R) も 694568バイト。
3つの合計で 2083704バイト。
Hinomaeさんの環境ではスタックサイズ 2MB に制限されていて、
他の変数も含めると、その合計で 2MB を超えてしまうのでしょう。
S も L も R も自動変数で関数に入るたびにスタック上に領域が確保されます。

main -> MergeSort -> MergeSort -> ... -> MergeSort -> Merge

MergeSort は再帰呼出しで 20回近く呼び出されますが、MergeSort 1つの変数の
サイズの合計は数10バイトなので、たいして問題になりません。

main と Merge で自動変数にしているのが良くないので、静的変数にしましょう。
static int S[N]; static int L[N], R[N]; のように書けばよいでしょう。

または、グローバル変数にすれば、静的変数になるので static は不要です。

Answer 3

MergeSortは再起関数になってて、実行されるたんびに、
int L[N],R[N];
がローカル変数で確保されるため、スタックがそれで食いつぶされるんでしょうね