mergesort unrecursive 归并排序的非递归实现

/*
 * mergesort_unrecursive.cpp
 *
 *  Created on: Dec 14, 2011
 *      Author: junfeng
 *
 //从分治策略的机制入手，容易消除归并排序算法中的递归，事实上，

 //算法Mergesort的递归过程只是将待排序列 集合一分为二，直到待排序列集合

 //只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以首先

 //将数组a中相邻元素两两配对。用合并算法将它们排序，构成n/2组长度为2的排好

 //序的子数组段，然后再将它们 排序成长度为4的排好序的子数组段，如此继续下去，

 //直至整个数组排好序。这就是自然合并排序的思想。对于n元数组已排好序情况

 //自然排序算法不执行合并，而算法mergesort需执行[logn]次合并。
 *
 *
 */

#ifndef MERGESORT_UNRECURSIVE_
#define MERGESORT_UNRECURSIVE_

#include<stdio.h>

void mergesort_unrecursive(int* a, const int n);
void print(int const * a, const int n);

int main()
{
	int a[] = { 1, 3, 2, 4, 5, -1, 0, -2, -3, -4, -5 };
	int len = sizeof(a) / sizeof(*a);

	print(a, len);
	mergesort_unrecursive(a, len);
	print(a, len);

	return 0;
}
void mergesort_unrecursive(int* a, const int n)
{
	int* b = new int[n];

	int len = 1;
	while (len < n)
	{
		/*
		 * 初始len==1
		 */
		int start = 0;
		int end = start + len;

		int k, start_max, end_max;
		while (start < n)
		{
			start_max = start + len;
			end_max = end + len;

			/*
			 * 处理一个小于len片断的情况
			 */
			if (start_max > n)
				break;//结束当前len的一次merge
			/*
			 * 处理最后一个长度len和小于len的两个片断
			 */
			if (end_max > n)
				end_max = n;//

			//			printf("start=%d\n", start);
			//			printf("start_max=%d\n", start_max);
			//			printf("end=%d\n", end);
			//			printf("end_max=%d\n", end_max);

			//复制merge的部分
			for (int i = start; i < end_max; i++)
				b[i] = a[i];

			/*
			 * end==start+len;
			 * merge [start,end]
			 * 		 [end,end+len]
			 */
			k = start;
			while (start < start_max && end < end_max)
			{
				if (b[start] < b[end])
					a[k++] = b[start++];
				else
					a[k++] = b[end++];
			}
			while (start < start_max)
				a[k++] = b[start++];
			while (end < end_max)
				a[k++] = b[end++];

			/*
			 * 下2个len的片断
			 */
			start = end_max;//这个开始错写尾s=end+len;
			end = start + len;

			//			printf("len=%d\n", len);
			//			printf("a=");
			//			print(a, n + 1);
		}
		len = len * 2;//开始错误:没有这句
	}

	delete[] b;
}
void print(int const * a, int const n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}
#endif //MERGESORT_UNRECURSIVE_