Return to Question

I've written this code for a merge sort, which is meant to implement the pseudo-code from Cormen's "Introduction to Algorithms":

(削除) When compiled and executed with this line: g++ -Wall merge_sort_exercise_1--kormen.cpp -O3 -o merge_sort && ./merge_sort

it crashes with a segmentation fault(core dumped). What did I do wrong?

Note: it's probably something having to do with array indices - I'm having trouble converting those that are used in the textbook pseudo-code into real C++ ones. Further Note: I'm reading the 2nd edition of the textbook, but I've also read that the 3rd introduces a parallel implementation of merge sort. Is there a canonical example? (削除ここまで)

Code has been fixed and now works and is worth reviewing as it horrible C++.

I've written this code for a merge sort, which is meant to implement the pseudo-code from Cormen's Introduction to Algorithms:

#include <iostream>
#include <cstdlib>
using namespace std;
const unsigned long long infinity = -1ULL;
void merge(int* A,int p,const int q, const int r)
{
 const int n_1=q-p+1;
 const int n_2=r-q;
 int* L = new int [n_1+1];
 int* R = new int [n_2+1];
 L[n_1]=infinity;
 R[n_2]=infinity;
 for(int i = 0; i < n_1; i++) 
 L[i] = A[p+i];
 for (int j = 0; j < n_2; j++)
 R[j] = A[q+j+1];
 
 int i=0;
 int j=0;
 for(int k = p; k <= r; p++)
 {
 if(L[i] <= R[j])
 {
 A[k] = L[i];
 i++;
 }
 else
 {
 A[k] = R[j];
 j++; 
 }
 } 
} 
 
void merge_sort(int* A, const int p, const int r)
{
 if (p < r) 
 {
 int q = (p+r)/2;
 merge_sort(A, p,q);
 merge_sort(A,q+1,r);
 merge(A,p,q,r);
 }
}
int main()
{
 int length;
 cout << "Specify array length" << endl;
 cin >> length;
 cout << "\n";
 int A [length];
 //Populate and print the Array
 for(int i = 0; i < length; i++)
 {
 A[i] = rand()%99-1;
 cout << A[i] << " ";
 } 
 cout << "\n";
 merge_sort(A,0,length-1);
 cout << "Your array has been merge_sorted and is now this: " << endl;
 for(int i = 0; i < length; i++) cout << A[i] << " ";
 
 cout << "\n";
 //cout << infinity << endl;
 return 0;
}

When compiled and executed with this line: g++ -Wall merge_sort_exercise_1--kormen.cpp -O3 -o merge_sort && ./merge_sort

it crashes with a segmentation fault(core dumped). What did I do wrong?

Note: it's probably something having to do with array indices - I'm having trouble converting those that are used in the textbook pseudo-code into real C++ ones. Further Note: I'm reading the 2nd edition of the textbook, but I've also read that the 3rd introduces a parallel implementation of merge sort. Is there a canonical example?

#include <iostream>
#include <cstdlib>
using namespace std;
const unsigned long long infinity = -1ULL;
void merge(int* A,int p,const int q, const int r)
{
 const int n_1=q-p+1;
 const int n_2=r-q;
 int* L = new int [n_1+1];
 int* R = new int [n_2+1];
 L[n_1]=infinity;
 R[n_2]=infinity;
 for(int i = 0; i < n_1; i++) 
 L[i] = A[p+i];
 for (int j = 0; j < n_2; j++)
 R[j] = A[q+j+1];
 
 int i=0;
 int j=0;
 // for(int k = p; k <= r; p++) broken code
 int k;
 for(k=p; k <= r && i < n_1 && j < n_2; ++k)
 {
 if(L[i] <= R[j])
 {
 A[k] = L[i];
 i++;
 }
 else
 {
 A[k] = R[j];
 j++; 
 }
  }
 // Added the following two loop.
 // Note only zero or one loop will actually activate.
 while (i < n_1) {A[k++] = L[i++];}
 while (j < n_2) {A[k++] = R[j++];}
} 
 
void merge_sort(int* A, const int p, const int r)
{
 if (p < r) 
 {
 int q = (p+r)/2;
 merge_sort(A, p,q);
 merge_sort(A,q+1,r);
 merge(A,p,q,r);
 }
}
int main()
{
 int length;
 cout << "Specify array length" << endl;
 cin >> length;
 cout << "\n";
 int A [length];
 //Populate and print the Array
 for(int i = 0; i < length; i++)
 {
 A[i] = rand()%99-1;
 cout << A[i] << " ";
 } 
 cout << "\n";
 merge_sort(A,0,length-1);
 cout << "Your array has been merge_sorted and is now this: " << endl;
 for(int i = 0; i < length; i++) cout << A[i] << " ";
 
 cout << "\n";
 //cout << infinity << endl;
 return 0;
}

(削除) When compiled and executed with this line: g++ -Wall merge_sort_exercise_1--kormen.cpp -O3 -o merge_sort && ./merge_sort

it crashes with a segmentation fault(core dumped). What did I do wrong?

Note: it's probably something having to do with array indices - I'm having trouble converting those that are used in the textbook pseudo-code into real C++ ones. Further Note: I'm reading the 2nd edition of the textbook, but I've also read that the 3rd introduces a parallel implementation of merge sort. Is there a canonical example? (削除ここまで)

Code has been fixed and now works and is worth reviewing as it horrible C++.

Note: it's probably something having to do with array indices - I'm having trouble converting those that are used in the textbook pseudo-code into real C++ ones. Further Note: I'm reading the 2nd edition of the textbook, but I've also read that the 3rd introduces a parallel implementation of it. Is there a canonical example?

Note: it's probably something having to do with array indices - I'm having trouble converting those that are used in the textbook pseudo-code into real C++ ones. Further Note: I'm reading the 2nd edition of the textbook, but I've also read that the 3rd introduces a parallel implementation of merge sort. Is there a canonical example?