Thread: sorting algo causing seg fault

any ideas on how I could fix this seg fault would be great! thanks!

Code:

template <typename I>
void merge(I begin, I mid, I end, bool (*compare)(typename I::value_type &x, typename I::value_type &y)) {
	int n1 = mid - begin;
	int n2 = end - mid;

	typedef typename I::value_type T;
	T* left = new T[n1];
	T* right = new T[n2];
	int i;

	//populate left and right arrays
	i = 0;
	for (I p=begin;i<n1;p++) {
		left[i] = *p;
		i++;
	}
	i = 0;
	for (I p=(mid);i<n2;p++) {
		right[i] = *p;
		i++;
	}

	T* result;
	i = 0;
	int leftCtr = 0;
	int rightCtr = 0;

	//Merge the two sorted arrays
	for (;i<n1+n2;i++) {
		if (leftCtr<n1 && rightCtr<n2) {
			if (compare(left[leftCtr],right[rightCtr])) {
				result[i] = left[leftCtr++];
			}
			else result[i] = right[rightCtr++];
		}
		else if (leftCtr<n1)
			result[i] = left[leftCtr++];
		else
			result[i] = right[rightCtr++];
	}
	i = 0;

	//Copy the sorted array back into the original array.
	for (I p=begin;p!=end;p++) {
		*p = result[i++];
	}
}



template<typename I>
void mergeSort(I begin, I end, bool (*compare)(typename I::value_type &x, typename I::value_type &y)) {

	int len = end - begin;

	if (len>1) {
		I mid = begin + (len/2);

		//Sort both the halves
		mergeSort(begin, mid, compare);
		mergeSort(mid, end, compare);
		merge(begin, mid, end, compare);
	}

	return;
}

Here's a better idea: compile the code in debug mode and run it in the debugger. When the seg fault occurs the debugger will stop when it occurs and you can evaluate the state of the program at the time of the crash. Where you're seg faulting, I'm going to assume you're on a *nix system and using gcc, in which case you would use gdb as your debugger. Debugging with GDB

Originally Posted by anon

You don't appear to allocate any memory for result.

(On the other hand it is unclear why you allocate extra arrays to make a copy of the ranges to be merged.)

thanks alot! that was exactly the problem.

ragstoriches - you are correct as well. when i ran it with gdb it was pretty apparent. strangely when i ran it with o3 optimization the gdb was actually more helpful than when i compiled without any optimizers.