归并排序的实现（c语言版本）

#include
#define ArrLen 20
void printList(int arr[], int len) {
	int i;
	for (i = 0; i < len; i++) {
		printf("%d ", arr[i]);
	}
}
void merge(int arr[], int start, int mid, int end) {
	int result[ArrLen];
	int k = 0;
	int i = start;
	int j = mid + 1;
	while (i <= mid && j <= end) 
	{
		if (arr[i] < arr[j]) 
		{
			result[k++] = arr[i++];
		}
		else 
		{
			result[k++] = arr[j++];
		}
	}
	if (i == mid + 1) 
	{
		while (j <= end)
			result[k++] = arr[j++];
	}
	if (j == end + 1) 
	{
		while (i <= mid)
			result[k++] = arr[i++];
	}
	for (j = 0, i = start; j < k; i++, j++) 
	{
		arr[i] = result[j];
	}
}

void mergeSort(int arr[], int start, int end) 
{
	if (start >= end)
		return;
	int mid = (start + end) / 2;
	mergeSort(arr, start, mid);//分
	mergeSort(arr, mid + 1, end);//分
	merge(arr, start, mid, end);//治
}

int main()
{
	int arr[] = { 4, 7, 6, 5, 2, 1, 8, 2, 9, 1 };
	mergeSort(arr, 0, 9);//传下标
	printList(arr, 10);
	system("pause");
	return 0;
}

主要是递归思想，先将大数组分成小数组，再重新组合小数组进行排序。