归并排序最简单的写法——只需要不到15行

众所周知，归并排序是一个稳定的，快速的排序算法，实现起来也比较容易，今天重温归并的时候发现了配合stl算法竟然可以写出一个这么短的归并排序。

当然，这个版本不具很好备泛型能力。

template <typename T>
void merge_sort(T arr[],int left,int right)
{
	if(left < right)
	{
		int mid = (left + right) / 2;
		merge_sort(arr, left, mid);
		merge_sort(arr, mid+1, right);
		vector<T> vec(right-left+1);
		merge(arr+left,arr+mid+1,arr+mid+1,arr+right+1,vec.begin());
		copy(vec.begin(),vec.end(),arr+left);
	}
}

这样写或许不够C++，是C加上模板，感觉有点不伦不类。下面这个改写的版本，虽然笔者没有写双向迭代器的版本，但是也具有很好的泛型，具备标准库似的泛型能力。能和STl很好的兼容，并且前闭后开的写法也使得这样更加容易阅读。

template <typename RandomIter>
void merge_sort_iter(RandomIter first, RandomIter last)
{
	if(first == last - 1)
		return;
	using distance_type = typename iterator_traits<RandomIter>::difference_type;
    distance_type dis = (last - first) / 2;
	auto mid = first + dis;
	merge_sort_iter(first,mid);
	merge_sort_iter(mid, last);
	using value_type = typename iterator_traits<RandomIter>::value_type;
	vector<value_type> vec(last-first);
	merge(first,mid,mid,last,vec.begin());
	copy(vec.begin(),vec.end(),first);
}

以后3分钟手搓一个差强人意的排序不是梦了。

ps: std::sort: 你说啥？