Merge Sort Recursive

Merge sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

									static void Merge(int* data, int left, int mid, int right) {
	int i, j, k;
	int n1 = mid - left + 1;
	int n2 = right - mid;
	int* L = new int[n1];
	int* R = new int[n2];

	for (i = 0; i < n1; i++)
		L[i] = data[left + i];

	for (j = 0; j < n2; j++)
		R[j] = data[mid + 1 + j];

	i = 0;
	j = 0;
	k = left;

	while (i < n1 && j < n2)
	{
		if (L[i] <= R[j])
		{
			data[k] = L[i];
			i++;
		}
		else
		{
			data[k] = R[j];
			j++;
		}

		k++;
	}

	while (i < n1)
	{
		data[k] = L[i];
		i++;
		k++;
	}

	while (j < n2)
	{
		data[k] = R[j];
		j++;
		k++;
	}

	delete L;
	delete R;
}

static void MergeSortRecursive(int* data, int left, int right) {
	if (left < right)
	{
		int m = left + (right - left) / 2;

		MergeSortRecursive(data, left, m);
		MergeSortRecursive(data, m + 1, right);
		Merge(data, left, m, right);
	}
}

Example

									int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
MergeSortRecursive(data, 0, 6);

Output