0

Hello,

I am trying to write the merge sort algorithm. My code is as follows:

```
#include <iostream>
#include <cstdlib>
using namespace std;
void m_sort(int list[], int temp[], int left, int right);
void merge(int list[], int temp[], int left, int mid, int right);
void mergeSort(int list[], int size)
{
int *temp = NULL;
temp = new int [ size / 2 + 1];
//int temp[2000000000];
m_sort(list, temp, 0, size - 1);
}
void m_sort(int list[], int temp[], int left, int right)
{
int mid;
if (right > left) {
mid = (right + left) / 2;
m_sort(list, temp, left, mid);
m_sort(list, temp, mid+1, right);
merge(list, temp, left, mid+1, right);
}
}
void merge(int list[], int temp[], int left, int mid, int right)
{
int left_end, num_elements, temp_pos;
left_end = mid - 1;
temp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right)) {
if (list <= list[mid]) {
temp[temp_pos] = list;
temp_pos = temp_pos + 1;
left = left + 1;
}
else {
temp[temp_pos] = list[mid];
temp_pos = temp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end) {
temp[temp_pos] = list;
left = left + 1;
temp_pos = temp_pos + 1;
}
while (mid <= right) {
temp[temp_pos] = list[mid];
mid = mid + 1;
temp_pos = temp_pos + 1;
}
for (int i=0; i <= num_elements; i++) {
list = temp;
right = right - 1;
}
}
int main (void)
{
int random[20];
for (int i = 0; i < 20; i++) {
random[i] = rand();
cout << random[i] << "\n";
}
cout << "\n";
mergeSort(random, 20);
for (int i = 0; i < 20; i++) {
cout << random[i] << "\n";
}
cout << "\n" << flush;
cout << "Merge sort of 20 items completed successfully \n" << flush;
cout << "\n" << flush;
int randomx[32000];
for (int foo = 0; foo < 32000; foo++) {
randomx[foo] = rand();
}
mergeSort(randomx, 32000);
cout << "Merge of 32000 items successfully finished. \n" << flush;
cout << "\n" << flush;
int randomz[32001];
for (int bar = 0; bar < 32001; bar++) {
randomz[bar] = rand();
}
mergeSort(randomz, 32001);
cout << "Merge of 32001 elements done \n" << flush;
cout << "\n" << flush;
return 0;
}
```

Now my problem is that the algorithm works for list size of 32000, but not for 32001. Why would this be and how can I go about fixing it?

Also, as a note:

Re-writing the code using std::vector, or passing temp[] in as an argument for mergeSort are not options, as they break the parameters of the assignment.