Merge Sort

[kevin06s]

Hello. I am trying to create a merge sort program, and am having trouble with passing around arrays.This is what I have so far:

#include <iostream>
using namespace std;

int* merge(int* leftHalf, int* rightHalf) {
	int leftIndex = 0, rightIndex = 0, sortedIndex = 0;
	int sorted[sizeof(leftIndex) + sizeof(rightIndex)];
	while(leftIndex < sizeof(leftHalf) && rightIndex < sizeof(rightHalf)) {
		if(leftHalf[leftIndex] < rightHalf[rightIndex]) {
			sorted[sortedIndex] = leftHalf[leftIndex];
			leftIndex++;
		}
		else {
			sorted[sortedIndex] = rightHalf[rightIndex];
			rightIndex++;
		}
		sortedIndex++;
	}
	
	while(leftIndex < sizeof(leftHalf)) {
		sorted[sortedIndex] = leftHalf[leftIndex];
		leftIndex++;
		sortedIndex++;
	}
	while(rightIndex < sizeof(rightHalf)) {
		sorted[sortedIndex] = rightHalf[rightIndex];
		rightIndex++;
		sortedIndex++;
	}
	return sorted;
}

int* mergeSort(int* list) {
	if(sizeof(list) <= 1) {
		return list;
	}
	
	int leftHalf[sizeof(list) / 2], rightHalf[sizeof(list) - sizeof(list) / 2];
	
	for(int i = 0; i < sizeof(list) / 2; i++) {
		leftHalf[i] = list[i];
	}
	for(int i = sizeof(list) / 2; i < sizeof(list); i++) {
		rightHalf[i - sizeof(list) / 2] = list[i];
	}
	
	leftHalf = mergeSort(leftHalf);
	rightHalf = mergeSort(rightHalf);
	
	list = merge(leftHalf, rightHalf);
	return list;
}

int main(int argc, char* argv[]) {
	int number[] = {2, 3, 4, 2, 5, 8, 2, 19, 3, 6, 2};
    mergeSort(number);


	cout << "The sorted numbers are: " << "\n";
	for(int i = 0; i < sizeof(number); i++) {
		cout << number[i] << "\n";
	}

	cin.get();
	return 0;
}

This results in these errors:
(29) : warning C4172: returning address of local variable or temporary
(46) : error C2440: '=' : cannot convert from 'int *' to 'int [2]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
(47) : error C2440: '=' : cannot convert from 'int *' to 'int [2]'
There are no conversions to array types, although there are conversions to references or pointers to arrays

How can I fix these errors?
Any help is appreciated.

[Computergeek01]

You need to use pointers friend. For the error you have on line 29, if you would pass a pointer into int merge(...) that referanced an array in your main function then there would be no need to return anything except a boolean pass\fail (Which I suggest as it gets you in the habit).

EDIT: This technique would fix all of your issues, I just wrote about the first error as an example, get back to us if you need more help.

[kevin06s]

How would I do that?
I thought an array was already a pointer?
Do I need to do merge(&leftHalf, &rightHalf)?
Or do I need to create a whole new pointer?

I also do not understand how I would only need to return a boolean. I need to combine both arrays into one, and return the new array. Are you saying I should just combine both into, say, leftHalf, and then return leftHalf as the combined one?

[ne555]

You're confused about sizeof. It returns how many bytes are needed to store the variable or type, and it's done in compilation time.
if you have something like this

int array[42], n, *ptr;
ptr = array;
n = sizeof(array) / sizeof(int); //n has  the length of the array
n = sizeof(ptr); //n has a value (probably 4) that corresponds to a pointer (direction of memory) 

In your function you must pass the length of the array, you can't calculate that
or use two pointers, begin and end [ )

Also your algorithm is incorrect

[ne555]

About the complains of your compiler.

(29) : warning C4172: returning address of local variable or temporary

the array sorted is created inside the function, and when the function ends it will be destroyed. So you are returning garbage.
But there is no need to return anything from your functions, so they could be void. (you've got parameter by reference)

(46) : error C2440: '=' : cannot convert from 'int *' to 'int [2]'
I thought an array was already a pointer

An array is a constant pointer, so you can't change the direction to what it points. Forget about the casting, the assignment is illegal.

[kevin06s]

Here is the new code:

#include <iostream>
using namespace std;

void merge(int* leftHalf, int* rightHalf, int* sorted) {
	int leftIndex = 0, rightIndex = 0, sortedIndex = 0;
	while(leftIndex < sizeof(leftHalf) && rightIndex < sizeof(rightHalf)) {
		if(leftHalf[leftIndex] < rightHalf[rightIndex]) {
			sorted[sortedIndex] = leftHalf[leftIndex];
			leftIndex++;
		}
		else {
			sorted[sortedIndex] = rightHalf[rightIndex];
			rightIndex++;
		}
		sortedIndex++;
	}
	
	while(leftIndex < sizeof(leftHalf)) {
		sorted[sortedIndex] = leftHalf[leftIndex];
		leftIndex++;
		sortedIndex++;
	}
	while(rightIndex < sizeof(rightHalf)) {
		sorted[sortedIndex] = rightHalf[rightIndex];
		rightIndex++;
		sortedIndex++;
	}
}

int* mergeSort(int list[]) {
	const int elements = (int)(sizeof(list) / sizeof(list[0]));
	const int midpoint = (int)(elements / 2);

	if(elements <= 1) {
		return list;
	}
	
	int leftHalf[midpoint], rightHalf[(elements - midpoint)];
	int* leftPtr = leftHalf,* rightPtr = rightHalf;

	for(int i = 0; i < midpoint; i++) {
		leftHalf[i] = list[i];
	}
	for(int i = midpoint; i < elements; i++) {
		rightHalf[i - midpoint] = list[i];
	}
	
	leftPtr = mergeSort(leftPtr);
	rightPtr = mergeSort(rightHalf);
	
	int sorted[elements];
	merge(leftHalf, rightHalf, sorted);
	return list;
}

int main(int argc, char* argv[]) {
	int number[] = {2, 3, 4, 2, 5, 8, 2, 19, 3, 6, 2};
    int* numberPtr = number;
	numberPtr = mergeSort(numberPtr);


	cout << "The sorted numbers are: " << "\n";
	for(int i = 0; i < sizeof(number) / sizeof(number[0]); i++) {
		cout << number[i] << "\n";
	}

	cin.get();
	return 0;
}

It produces
error C2466: cannot allocate an array of constant size 0
error C2133: 'leftHalf' : unknown size

It used to be that I got those two errors for both leftHalf and rightHalf, so I made element and midpoint const ints, and now only leftHalf produces the unknown size error. How can I fix this?

[ne555]

//int* mergeSort(int list[]) list is a pointer, so in this way you can't know the numbers of element.
//Use
void mergeSort(int list[], int nelements)
void mergeSort(int *begin, int *end) // [ )   the number of elements is end - begin
//no need to return anything 

You will need to allocate your array dynamical.

int *sorted = new int [nelements];
//and when you finish using it
delete [] sorted;

At the end of your function list must be ordered, but you don't modify it.
Do the partition in place, (left and right will be ranges in list, not copies)
merge them using an temporal, (new and delete)
and then copy the values to list again (not the pointers, the actual values)