Mergesort(nlogn)

算法：使用recursion将数组不断二分，最终比较两个数并排序，然后将以排序的两个sub-array再排序merge到另一个array，不断重复…
代码：

#include <stdio.h>
#define SIZE 7

void MergeSort();
void Merge();
void PrintArray();

int main()
{
	int arr[SIZE] = {1, 5, 34, 64, 43, 3, 34};
	
	MergeSort(arr, 0, SIZE - 1);
	printf("sorted array: \n");
	PrintArray(arr, SIZE);
	
	return 0;
}

void PrintArray(int* arr, int size)
{
	int i;
	for (i = 0; i < size; i++) {
		printf("%i ", arr[i]);
	}
	printf("\n");
}

void MergeSort(int* arr, int left, int right)
{
	if (left < right)
	{
		int middle = (left + right) / 2;
		
		MergeSort(arr, left, middle);
		MergeSort(arr, middle + 1, right);
		Merge(arr, left, middle, right);
	}
}

void Merge(int* arr, int left, int middle, int right)
{
	int i, j, k;
	int n1 = middle - left + 1;
	int n2 = right - middle;
	int L[n1], R[n2];
	
	for (i = 0; i < n1; i++) {
		L[i] = arr[left + i];
	}
	for (j = 0; j < n2; j++) {
		R[j] = arr[middle + 1 + j];
	}
	
	i = 0;
	j = 0;
	k = left;
	
	while (i < n1 && j < n2)
	{
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	
	while (j < n2) {
		arr[k] = R[j];		
		j++;
		k++;
	}
}