/<span id="_xhe_cursor"></span>/ 归并排序
// O(NlogN),所以归并排序最坏情况能够达到快速排序的平均水准
// 需要额外的存储空间O(n)

// 1、对数据不断的分割，直到剩下一个一个的
// 2、合并数据，在合并的时候，其实是两个有序的数组，因此
//    这个过程是两个有序数组进行合并排序


#include "sort.h"

// merge函数实现了合并的过程
// i为数组最小索引,j为中间值，k为最大索引值
int merge(void *data, int size, int esize, int i, int k, int j,
		  int (*compare)(const void *key1, const void *key2))
{
	int ipos, jpos, mpos;	// i, j， m的游标
	int *a = (int *)data;
	int *m;					// 申请的m的额外空间
	if ((m = (int *)malloc(sizeof(int) * size)) == NULL)
	{
		return -1;
	}

	memcpy(m, 0, sizeof(int) * size);

	ipos = i;
	jpos = j;		// j为中间值
	mpos = 0;



	while (ipos <= j || jpos <= k)
	{
		while (ipos <= j && jpos >= k)	// 当就剩下i的索引没有到中间
		{
			memcpy(&m[mpos], &a[ipos], sizeof(int));
			ipos++;
			mpos++;
		}

		while (ipos >= j && jpos <= k) // 当就剩下j的索引没有到中间
		{
			memcpy(&m[mpos], &a[jpos], sizeof(int));
			jpos++;
			mpos++;
		}

		if (compare(&a[ipos], &a[jpos]) <= 0 )	// 小的数先插入到m临时序列
		{
			memcpy(&m[mpos], &a[ipos], sizeof(int));
			ipos++;
			mpos++;
		}
		else
		{
			memcpy(&m[mpos], &a[jpos], sizeof(int));
			jpos++;
			mpos++;
		}
	}

	data = http://www.mamicode.com/m;	// 返回data，此时已完成排序>

算法精解（三）——归并排序