7.归并排序

7.1 描述
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。 
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列
7.2 复杂程度
时间复杂度O(nlog2n)                 空间复杂度O(n)
7.3 代码 
#include<stdio.h>
#include<assert.h>
#include<stdlib.h> 
#define ArrLen 20
void printList(int arr[], int len) 
{
	int i;
	for (i = 0; i < len; i++) 
	{
		printf("%d\t", 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[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
	mergeSort(arr, 0, 13);
	printList(arr, 14); 
	return 0;
}

7.4 运行时间
0.02142s