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.

does it work for 32002?

No; it does not work for any value larger than 32000.

I get a compile error on line 39:

``if (list <= list[mid])``

ISO C++ forbids comparison between pointer and integer

Is this the small "doesn't work" because it no longer sorts?
Or a larger "DOESN'T WORK" because the program crashes with some bizarre error message?

I see a lot of scope for blowing the stack with the large number of large arrays on the stack.

Does 32001 BY ITSELF work?

Consider

``````int main ( ) {
int sizes[] = { 20, 200, 2000 };
for ( int s = 0 ; s < sizeof(sizes)/sizeof(sizes[0]) ; s++ ) {
int size = sizes[s];

int *random = new int[size];
for (int i = 0; i < size; i++) {
random[i] = rand();
cout << random[i] << "\n";
}
cout << "\n";

mergeSort(random, size);

for (int i = 0; i < size; i++) {
cout << random[i] << "\n";
}

cout << "\n" << flush;
cout << "Merge sort of 20 items completed successfully \n" << flush;
cout << "\n" << flush;
delete [] random;
}
}``````

Your code is essentially a copy/paste job with different sizes.

The 'doesn't work' is actually a segmentation fault.

Shockingly, 32001 DOES work by itself...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.