非递归版的归并排序，省略了中间的栈空间，直接申请一段O(n)的地址空间即可，因此空间复杂度为O(n),时间复杂度为O(nlogn);
算法思想：
开始以间隔为1的进行归并，也就是说，第一个元素跟第二个进行归并。第三个与第四个进行归并；
然后，再以间隔为2的进行归并，1-4进行归并，5-8进行归并；
再以2*2的间隔，同理，知道2*k超过数组长度为止。
while(i<length){ Merge(arr,temp,i,length); i *= 2; }
当不够两组进行归并是，如果超过k个元素，仍然进行归并；如果剩余元素不超过k个元素，那么直接复制给中间数组。
while(i <= length-2*k){ sort(arr1,temp,i,i+k-1,i+2*k-1); i += 2*k; }
if(i < length-k+1)//如过剩余个数比一个k长度还多...那么就在进行一次合并 sort(arr1,temp,i,i+k-1,length-1); else for(j=i;j<length;j++) temp[j] = arr1[j];
主要代码：
void MergeSort(int *arr,int length){ int *temp = (int *)malloc(sizeof(int)*length); int i = 1; while(i<length){ Merge(arr,temp,i,length); i *= 2; } } void Merge(int *arr1,int *temp,int k,int length){ int i = 0,j; while(i <= length-2*k){ sort(arr1,temp,i,i+k-1,i+2*k-1); i += 2*k; } if(i < length-k+1)//如过剩余个数比一个k长度还多...那么就在进行一次合并 sort(arr1,temp,i,i+k-1,length-1); else for(j=i;j<length;j++) temp[j] = arr1[j]; for(i=0;i<length;i++){ arr1[i] = temp[i]; } } void sort(int *arr3,int *arr1,int begin,int m,int end){ int i=begin,j=m+1,k,h; for(k=i; i<=m && j<=end;k++){ if(arr3[i] < arr3[j]) arr1[k] = arr3[i++]; else arr1[k] = arr3[j++]; } if(i <= m){ for(h=0; h<=m-i;h++) arr1[k+h] = arr3[i+h]; }else{ for(h=0; h<=end-j;h++) arr1[k+h] = arr3[j+h]; } }
全部代码：
#include <stdio.h> #include <stdlib.h> #include <time.h> int arrtest1[10] = {4,3,7,8,0,9,1,2,6,5}; int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9}; int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0}; void copy(int *from,int *arr,int length); void print(int *arr,int length); void MergeSort(int *arr,int length); void Merge(int *arr1,int *temp,int k,int length); void sort(int *arr3,int *arr1,int begin,int m,int end); int main(){ int Arr[10],i; copy(arrtest1,Arr,10); print(Arr,10); MergeSort(Arr,10); print(Arr,10); getchar(); return 0; } void MergeSort(int *arr,int length){ int *temp = (int *)malloc(sizeof(int)*length); int i = 1; while(i<length){ Merge(arr,temp,i,length); i *= 2; } } void Merge(int *arr1,int *temp,int k,int length){ int i = 0,j; while(i <= length-2*k){ sort(arr1,temp,i,i+k-1,i+2*k-1); i += 2*k; } if(i < length-k+1)//如过剩余个数比一个k长度还多...那么就在进行一次合并 sort(arr1,temp,i,i+k-1,length-1); else for(j=i;j<length;j++) temp[j] = arr1[j]; for(i=0;i<length;i++){ arr1[i] = temp[i]; } } void sort(int *arr3,int *arr1,int begin,int m,int end){ int i=begin,j=m+1,k,h; for(k=i; i<=m && j<=end;k++){ if(arr3[i] < arr3[j]) arr1[k] = arr3[i++]; else arr1[k] = arr3[j++]; } if(i <= m){ for(h=0; h<=m-i;h++) arr1[k+h] = arr3[i+h]; }else{ for(h=0; h<=end-j;h++) arr1[k+h] = arr3[j+h]; } } void copy(int *from,int *arr,int length){ int i; for(i=0;i<length;i++){ arr[i] = from[i]; } } void print(int *arr,int length){ int i; for(i=0;i<length;i++){ printf("%d ",arr[i]); } printf("\n"); }
运行实例：
本文转自博客园xingoo的博客，原文链接：非递归版归并排序，如需转载请自行联系原博主。
