マージソート C++

Question

C++でコードを書くのは初めてです。
マージソートを実装したく、下記のコードを書いてみたのですがうまくいきません。
具体的に言うとソートされておらず、入力したままの配列が表示されます。
詳しい方いらっしゃったらご教授お願い致します。

#include<iostream>
#include<limits>

void mergeSort(int* A, int left, int right);
using namespace std;
int ct=0;
int main() {
	int* S;
	int n;
	cin >> n;
	S = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> S[i];
	}
	/*for (int i = 0; i < n; i++) {
		cout << S[i];
		cout << " ";
	}*/

	mergeSort(S,S[0],S[n-1]);

	for (int i = 0; i < n-1; i++) {
		cout <<  S[i];
		cout << " ";
	}
	cout << S[n - 1] << endl;
	cout << ct<<endl;
}

void merge(int* A ,int left, int mid, int right) {
	int n1 = mid - left;
	int n2 = right - mid;
	int* L;
	int* R;
	L = new int[n1];
	R = new int[n2];
	for (int i = 0; i < n1 - 1; i++) {
		L[i] = A[left + i];
	}
	for (int i = 0; i < n2 - 1; i++) {
		R[i] = A[mid + i];
	}
	L[n1] = INFINITY;
	R[n2] = INFINITY;
	int i = 0;
	int j = 0;
	
	for (int k = left; i < right - 1; i++) {
		if (L[i] <= R[j]) {
			A[k] = L[i];
			i = i + 1;
			ct++;
		}
		else {
			A[k] = R[j];
			j = j + 1;
		}
	}
}

void mergeSort(int* A, int left, int right) {
	if (left + 1 < right) {
		int mid = (left + right) / 2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}

Answer 1

mergeSort(S,S[0],S[n-1]);

    mergeSort(S,0,n-1);

が正しいでしょう。

L = new int[n1];
R = new int[n2];

後にL[n1]およびR[n2]に代入しちゃっているので、それぞれ+1しないといけません。

最後に、newで確保したメモリを解放していないのが気になります。

Comments

[aufheben]

mergeSortの引数とL=new int[n1+1],R=new int[n2+1]を修正したところ、実行結果が
3 5 -1574969728 2 -572662307 3 0 0 10 4
20
などランダムで変わるようになってしまいました。
動的配列の確保の仕方が間違っているんでしょうか？
あとdelete[]はどこに入れればいいんでしょうか？
mergeの最後にdelete[]を入れると何も表示されませんでした。

[asm]

結果がランダムになるのは
> for (int k = left; i < right - 1; i++) {
ここの i < right - 1 およびi++はk < right および k++の間違いですね

mergeラストでLおよびRをdelete[]する事が必要です

まぁnew/deleteは、言ってしまえば古いC++の習慣です
配列を動的確保したいならvectorを使った方が安全です。
https://qiita.com/asm/items/b27f5f40f51d3fd32fd7
↑暇だからえせモダンでマージソートを実装するとこうなりましたmergeラストでLおよびRをdelete[]する事が必要です

ご質問のコードをバグ取りしたら以下になりました。
デバッグ用のログ出力はそのままにしておきます。
https://wandbox.org/permlink/VBExhh2VrQS00umr

[aufheben]

丁寧な説明ありがとうございました！

Answer 2

回答ではないですが、
Windowsを使っているなら、VisualStudioを使ってデバッグしてみてはどうでしょう
ソースコード上の任意の行にブレークポイントを設置し、実行をそこで止め、各変数の内容を参照することができます。
また、1行づつ実行し、変数の内容をモニタするようなこともできます