Merge sort: Works for list size of 32000, but not for 32001. Why?

[ItecKid]

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.

[jbennet]

does it work for 32002?

[ItecKid]

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

[VernonDozier]

I get a compile error on line 39:

if (list <= list[mid])

ISO C++ forbids comparison between pointer and integer

[Salem]

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.

[ItecKid]

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

Shockingly, 32001 DOES work by itself...