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

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


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

/<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 = m;	// 返回data，此时已完成排序

	free(m);	// 最后释放m

	return 0;
}



// 排序函数
int mgsort(void *data, int size, int esize, int i, int k,
		   int (*compare)(const void *key1, const void *key2))
{
	int j;

	if (i < k)
	{
		j = (k + i - 1) / 2;	// 让j取中间值

		if (mgsort(data, size, esize, i, j, compare) < 0)// 不断的分割左边，递归后合并
		{
			return -1;
		} 

		if (mgsort(data, size, esize, j+1, k, compare))// 分割右边
		{
			return -1;
		}

		if (merge(data, size, esize, i, k, j, compare) < 0)
		{
			return -1;
		}
	}

	return 0;
}