归并排序：先对两个有序的系列进行合并，合并的时候不断的对两个系列的第一个元素进行比较，把较小的那个移动到最前面成为了第一个元素，那么移动的元素后面的元素就是成为了下次比较的序列的第一个元素，如此不断的取两个系列的第一个元素进行比较。

1 4 5 6     2 7 8 9      第一轮1与2比较  1比2小， 那么1被移动了   4成为了下次要比较的元素了

那么下一轮就是比较4和2   2小就被移动了  那么再次比较的就是4和7了  如此一轮一轮的比较。

//merge two array：对两个有序列进行合并
void merge(int a[], int temp[], int first, int mid, int end)
{
	int i = first, j = mid + 1;
	int m = mid, n = end;
	int k = 0;

	while (i <= m && j <= n)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}

	while (i <= m)
		temp[k++] = a[i++];
	while (j <= n)
		temp[k++] = a[j++];

	for (int i = 0; i < k; i++)/*把存储在临时对象temp中排好序列copy到a中对应的下标上*/
		a[first + i] = temp[i];
}

void merge_sort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		merge_sort(a, first, mid, temp);    //it's let letf have a regular
		merge_sort(a, mid + 1, last, temp); //it's let right have a regular
		merge(a, temp, first, mid, last); //merge two  in  one  
	}
}

写个测试代码：

int main()
{
	int a[] = { 1, 8, 6, 7, 9, 45, 68, 100, 5 };

	int k = (sizeof(a) / sizeof(int));

	int *p = new int[k];

	merge_sort(a,0,k-1,p);

	for (int i = 0; i < k; i++)
		cout << a[i] << " ";

	return 0;
}

归并排序算法的理解