非递归版的归并排序，省略了中间的栈空间，直接申请一段O(n)的地址空间即可，因此空间复杂度为O(n),时间复杂度为O(nlogn);

实现：

#include<stdio.h>
#include<stdlib.h>

void merge1(int a[], int tmp[], int left, int right, int r_end)//实际例程 
	{
		int tmp_pos, l_end;
		int element_num;
		tmp_pos = left;
		l_end = right-1;
		element_num = r_end-left+1;
		
		while(left <= l_end && right <= r_end){
			if(a[left] <= a[right]){
				tmp[tmp_pos++] = a[left++];
			}
			else
				tmp[tmp_pos++] = a[right++];
		}
		while(left <= l_end){
			tmp[tmp_pos++] = a[left++];
		}
		while(right <= r_end){
			tmp[tmp_pos++] = a[right++];
		}	
	} 
void merge_once(int a[], int tmp[], int n, int step)//当前step下的一趟 
	{
		int i;
		int j; 
		for(i = 0; i <= n-2*step; i += 2*step ){//保证只合并完整的两个子序列 
			merge1(a, tmp, i, i + step, i + 2*step - 1);
		}
		//结束时 i 跳到下一次归并子序列起点（如果还有子序列的话） 
		if(i + step < n+1)// 判断是否超过一个子序列（不会是2个子序列） 
			merge1(a, tmp, i, i+step, n-1);
		else{
			for(j = i; j < n; j++ )
				tmp[j] = a[j]; 
		}	
//*************************************//
//下面这个 保证每次 归并完 都把结果 重新保存到数组 a中	//
//*************************************//	
		for(i = 0; i < n; i++ ){
			a[i] = tmp[i];
		}	
	}

void merge_sort(int a[], int n) //驱动程序 
	{
		int *tmp;
		int step = 1;
		tmp = (int *)malloc(sizeof(int)*n);// 不要忘记 乘 n 
		if(tmp != NULL){
			while(step < n){
				merge_once(a, tmp, n, step);
				step *= 2;
	//下面这个 同样是保证最后的结果都保存在 a 数组中 并且比上面的方法更高效//
//************************************************************//								 	
//				merge_once(tmp, a, n, step);              //
//				step *= 2; 								 //
//******************************************************//
			}
		}
	}	

int main()
	{
		int a[] = {5, 6, 8, 1, 10, 23, 12, 2, 9, 11};
		int n;
		n = sizeof(a)/sizeof(a[0]);
		merge_sort(a, n);
		
		int i;
		for(i = 0; i < n; i++ ){
			printf("%d ",a[i]);
		}
		
		return 0;	
	}