归并排序迭代实现

#include <stdio.h>
#include <stdlib.h>//导入malloc所需头文件

void mergesort(int num[],int len);
int main(){
	int num[10] = {5,2,6,0,3,9,1,7,4,8};//待排序数组 

	mergesort(num,10);

	for(int i = 0; i<10 ;i++){
		printf("%d ",num[i]);
	}
}

void mergesort(int num[],int len){
	//对数组num归并排序迭代实现,len为数组长度，从小到大排序，O(nlog2^n)，稳定
	/*核心思想，i表示步长，也就是左右两组各几个元素比较
		，从第一轮左右每组1个开始，每轮步长增大一倍
		，比较后从小到大存入temp，再对剩余元素进行处理
		，最后将排好序的temp返回num数组
		*/

	//分别为步长、temp下标、左边起始下标、左边终点下标、右边起始下标、右边终止下标
	int i,next,left_min,left_max,right_min,right_max;
	//新建一个temp数组，长度等于初始数组长度
	int *temp = (int*)malloc(len * sizeof(int));

	//每轮比较左右两个步长i长度的区间，每轮后i*=2
	for(i=1; i<len; i*=2){

		//从数组0号开始，下一组的起始位置等于上一组的终止位置，如果下一组左边步长都不够就不比了
		for(left_min=0; left_min < len-i; left_min = right_max){
			//右边起始位置=左边终止位置=左边起始加步长i
			right_min = left_max = left_min + i;
			//右边终止位置=右边起始位置加步长i
			right_max = right_min + i;
			next = 0;//temp的下标

			if(right_max > len){//如果右边越界
				right_max = len;//右边终止位置最大值只能为len
			}

			while(left_min < left_max && right_min < right_max){//左右都没到尽头
				if(num[left_min] < num[right_min]){//左小右大，左边存入temp
					temp[next++] = num[left_min++];
				}else{//右小左大，右边存入temp
					temp[next++] = num[right_min++];
				}
			}

			/*左边还有一组剩余元素，右边已到终止位置
				，说明左边剩余元素最大，将剩余元素移到右边最后
				，如果是右边有剩余，则不需要移了已经在最后*/
			while(left_min < left_max){
				num[--right_min] = num[--left_max];
			}

			while(next > 0){//把排好序的temp部分返回num
				 num[--right_min] = temp[--next];
			}
		}
	}
}