本文为senlie原创。转载请保留此地址：http://blog.csdn.net/zhengsenlie

merge sort

----------------------------------------------------------------------

描写叙述：归并排序

思路：

1.将区间对半切割

2.对左、右段分别排序

3.利用inplace_merge将左、右段合并成为一个完整的有序序列





复杂度：O(nlog n)

源代码：

template<class BidirectionalIter>

void mergesort(BidirectionalIter first, BidirectionalIter last){

	typename iterator_traits<BidirectionalIter>::diference_type n = distance(first,last);

	if(n == 0 || n == 1) return ;

	else{

		BidirectionalIter mid = first + n / 2;

		mergesort(first, mid);

		mergesort(mid, last);

		inplace_merge(first, mid, last);

	}

}

演示样例：

int main()

{

	int a[]={3,8,0,6,7,4,2,1,9,3,1,8,3,9,2,0,9};

	int *a_end=a+sizeof a/sizeof(int);

	std::cout<<"a before mergesort: ";

	std::for_each(a, a_end, print<int>);

	std::cout<<'\n';

	mergesort(a, a_end);

	std::cout<<"a after mergesort: ";

	std::for_each(a, a_end, print<int>);

	std::cout<<'\n';

	return 0;

}