学步园

归并是O（NlogN）里比较快的，通常速度非常接近快排。思想也是分治。

比如现在有a[0~n]需要排序

tips：1.先让a[1 ~ n/2]和a[1 ~ n/2 + 1]分别有序，回溯的时候再合并起来；

 2.既然左右两半都各自有序，那么比较其各自第一个元素大小，并不断插入到一个临时数组里即可；

	while(i <= mid && j <= right)
	{
		if (a[i] < a[j])
		{
			tmp[k++] = a[i++];
		}
		else
			tmp[k++] = a[j++];		
	}
	while(i <= mid)
	{
		tmp[k++] = a[i++];
	}
	while(j <= right)
	{	
		tmp[k++] = a[j++];
	}

这里k = right - left, 即本次被合并的俩子数列的总长。

 3.递归地划分数列，再合并起来。递归终止于数列只存在1个元素，即left == right的情况。

void mergesort(int a[], int left, int right, int tmp[])
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		mergesort(a, left, mid, tmp);
		mergesort(a, mid+1, right, tmp);
		merge(a, left, mid, right, tmp);
	}
}

 4.白话经典算法中为了省掉每次分配临时数组的时间，在最上层统一分配了一个大tmp数组，送进程序。

完整codes:

#include <iostream>
using namespace std;

void merge(int a[], int left, int mid, int right, int tmp[])
{
	int i, j, k;
	k = 0;
	i = left;
	j = mid + 1;
	while(i <= mid && j <= right)
	{
		if (a[i] < a[j])
		{
			tmp[k++] = a[i++];
		}
		else
			tmp[k++] = a[j++];		
	}
	while(i <= mid)
	{
		tmp[k++] = a[i++];
	}
	while(j <= right)
	{	
		tmp[k++] = a[j++];
	}

	for (i = 0; i < k; ++i)
	{
		a[left + i] = tmp[i];
	}
}

void mergesort(int a[], int left, int right, int tmp[])
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		mergesort(a, left, mid, tmp);
		mergesort(a, mid+1, right, tmp);
		merge(a, left, mid, right, tmp);
	}
}

bool Mergesort(int a[], int n)
{
	int* tmp = new int[n];
	if (tmp == NULL)
	{
		return false;
	}
	mergesort(a, 0, n-1, tmp);

	delete[] tmp;
	return true;
}

int main(void)
{
	int a[] = {2,4,5,6,1,9,10,3,8,7};

	Mergesort(a, 10);

	for (int i = 0; i < 10; ++i)
	{
		cout << a[i] << endl;
	}

	return 0;
}