数组版本的归并排序

merge_sort.c

#include <cstdio>

void merge(int* input, int* left, int nLeft, int* right, int nRight)
{
	int i = 0;

	// copy until one array ends
	int l = 0, r = 0;
	while(l < nLeft && r < nRight)
	{
		if(left[l] < right[r]) input[i++] = left[l++];
		else if(left[l] > right[r]) input[i++] = right[r++];
		else {input[i++] = left[l++]; input[i++] = right[r++];}
	}

	// copy the tail
	int* p = (l == nLeft) ? right + r : left + l;
	int n =  (l == nLeft) ? (nRight - r) : (nLeft - l);
	int j = 0;
	while(n--) input[i++] = p[j++];
	
}

// Time: O(nlgn)
// Space: O(n)
void merge_sort(int* input, int size)
{
	if(size < 2) return; // just return if size == 1

	int mid = size / 2;

	// left:  [start, mid) 
	// right: [mid, end]

	// copy left and merge
	int nleft = mid;
	int* left = new int[nleft];
	int* origLeft = input;

	int nleft_copy = nleft;
	int* left_copy = left;
	while (nleft_copy--) *left_copy++ = *origLeft++;
	if(nleft > 1)
		merge_sort(left, nleft);

	// copy right and merge
	int nright = size - mid;
	int* right = new int[nright];
	int* origRight = input + mid;

	int nright_copy = nright;
	int* right_copy = right;
	while(nright_copy--) *right_copy++ = *origRight++;
	if(nright > 1)
		merge_sort(right, nright);

	// merge left and right
	merge(input,left, nleft, right, nright);

	delete [] left;
	delete [] right;

}

int main(int argc, const char* argv[])
{
	// 1 element
	{
		int input[] = {2};
		int len = sizeof(input) / sizeof(input[0]);
		merge_sort(input, len);
		int i = 0;
		while(len--) printf("%d ", input[i++]);
		printf("\n");
	}

	// 2 elements
	{
		int input[] = {2, 0};
		int len = sizeof(input) / sizeof(input[0]);
		merge_sort(input, len);
		int i = 0;
		while(len--) printf("%d ", input[i++]);
		printf("\n");
	}

	// multiple elements
	{
		int input[] = {2, 1, -4, 8, 6, 9, 9, 1, 4};
		int len = sizeof(input) / sizeof(input[0]);
		merge_sort(input, len);
		int i = 0;
		while(len--) printf("%d ", input[i++]);
		printf("\n");
	}
	
}