C++でマージソートのコーディングがうまく行きません！！

前提・実現したいこと

Aizu Online Judgeのアルゴリズムの問題で、与えられた数字をマージソートで昇順に並べ替えようとしています。
問題文
「n個の整数を含む数列Sを上の疑似コードに従ったマージソートで昇順に整列するプログラムを作成してください。また、mergeにおける比較回数の総数を報告してください。

入力
１行目にn、２行目にSを表すn個の整数が与えられます。

出力
１行目に整列済みの数列Sを出力してください。数列の隣り合う要素は１つの空白で区切ってください。２行目に比較回数を出力してください。」
url(https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B)

発生している問題・エラーメッセージ

要素数が少ない場合は問題なく機能するのですが、最後の500000個の数字が与えられた場合のみ以下のエラーが発生してしまいます。

timeout: the monitored command dumped core 0.14user 0.00system 0:00.34elapsed 42%CPU (0avgtext+0avgdata 5060maxresident)k 0inputs+8outputs (0major+784minor)pagefaults 0swaps

該当のソースコード

C++
1#include <bits/stdc++.h>
2#define INF 10000000
3using namespace std;
4void marge(vector<int>&S,int left, int right, int mid, int &cnt){
5  int n1 = mid - left;
6  int n2 = right - mid;
7  vector<int> L(n1+1),R(n2+1);
8  for(int i=0;i<n1;i++)L[i]=S[left+i];
9  for(int i=0;i<n2;i++)R[i]=S[mid+i];
10  int i=0,j=0;
11  L[n1]=INF,R[n2]=INF;
12  for(int k=left; k<right; k++){
13    if(L[i] <= R[j]){
14      cnt ++ ;
15      S[k]=L[i];
16      i++;
17    }
18    else{
19      cnt ++ ;
20      S[k]=R[j];
21      j++;
22    }
23  }
24}
25
26void margeSort(vector<int>&S,int left, int right, int &cnt){
27  if(left+1<right){
28    int mid=(left+right)/2;
29    margeSort(S,left,mid,cnt);
30    margeSort(S,mid,right,cnt);
31    marge(S,left,right,mid,cnt);
32  }
33  return;
34}
35      
36int main(){
37  int count=0,n;
38  cin >> n;
39  vector<int> S(n);
40  for(int i=0;i<n;i++)cin >> S[i];
41  margeSort(S, 0, n, count);
42  for(int i=0;i<n;i++){
43    if(i!=n-1)cout << S[i] << " ";
44    else cout << S[i] << endl;
45  }
46  cout << count << endl;
47}

試したこと

LRの両者のn1,n2部分に代入する数値を定義した。

補足情報（FW/ツールのバージョンなど）

当方、文系学生で、基礎的な数学の知識も持ち合わせていないので、可能であれば、答えより着眼点・原因発見のヒントやどう言うふうに考えるといいと言うようなアドバイスをいただけると今後の学習に活かせそうなのでありがたいです！！

y_waiwai

2021/09/27 05:39

そのエラーメッセージって、なにが出してるメッセージなんでしょうか。コンパイルエラーのたぐいじゃないですよね。

BeatStar

2021/09/27 05:39

とりあえず、もとの質問(Aizu)の問題があるURLも載せてください。もしかすると前提そのものが違う可能性があります。有名なアルゴリズムでも特定の条件によっては逆に遅くなるときがありますし。

fana

2021/09/27 05:46

（処理は見てないけど）とりあえずぱっと見で vector<int> L(n1+1),R(n2+1); これを毎回作っては捨てるのが時間食いそうにも思えるが，実際どんなもんだろう？

退会済みユーザー

2021/09/27 06:09

もし、ALDS1_5_B問題のことであれば、入力値の最大は 10^9です。INFの値が小さすぎます。またプログラム動作とは関係ありませんが、margeじゃなくてmergeです。

kangaroo

2021/09/27 06:10

回答ありがとうございます！エラーの原因は計算量が多いのか、原因はわからないのですが、時間がかかりすぎてしまうことなのではないかと考えています。問題文の載っているURLは以下のものです！ https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B 問題文は「n個の整数を含む数列 Sを上の疑似コードに従ったマージソートで昇順に整列するプログラムを作成してください。また、mergeにおける比較回数の総数を報告してください。入力１行目に n、２行目に Sを表す n個の整数が与えられます。出力１行目に整列済みの数列 Sを出力してください。数列の隣り合う要素は１つの空白で区切ってください。２行目に比較回数を出力してください。」なるほど、vector<int>L,Rの部分を関数街で定義して、一々新しくしなくてもいい状態にして試してみようと思います！！

kangaroo

2021/09/27 06:16

問題まさにそれです！！なるほど、そこの条件の部分、めちゃくちゃ重要ですね笑 INFの定義を修正したら解決しました！！簡単な問題ばかり解いて、条件の部分を意識しないできたのが明らかな原因でした！綴りのミスは多めに見て欲しいです汗

行動規範の内容に同意します

回答1件

自己解決

INFの値を10^9にすることで解決しました！！
問題の条件をしっかり見ないでいたためにミスを犯していたように思います。

みなさん回答ありがとうございました！！
めちゃくちゃ参考になりました！

投稿2021/09/27 06:19

kangaroo

総合スコア2

fana

2021/09/27 06:30

番兵が入力値の最大値と同じ値でも大丈夫なのだろうか？　ってのが不安になりませんか？（問題が起きる入力パターンがたまたまテストパターンに無かっただけなのか，それもとも本当に大丈夫なのか？　は知りませんが……　私なら，とにかく確実に「番兵」の役割を果たす値として，　入力の最大値よりもでかい値　にしておく．）

kangaroo

2021/09/27 10:05

ご指摘ありがとうございます！確かに！！考えてみると与えられた条件を確実に満たす値にはなっていなかったように思えます… 仮に今回でいう10^9と同じ値の要素が与えられた場合、今回指定した最大値では確実性に欠く部分が多いように思えてきました！！条件部分を確認した上で、最大値は確実に条件式よりも大きな値を取るように気をつけてみようと思います！！

行動規範の内容に同意します