根号n分治排序的C语言实现：
算法课的这样一道题目
根号n段合并排序算法：
将数组 划分为 根号n个子数组，每个子数组有 根号n个元素。然后递归地对分割后的子数组进行排序，最后将所得到的 个排好序的子数组合并排序。
分治算法 思想：
首先随机生成一个数组，把数组和一个临时存放数据的数组传入函数RadicalSort（）并且传入数组的头位置和尾位置
RadicalSort（）函数中在头位置小于尾位置的时候调用，把数组分治为√n份递归的处理每个数组的问题，注意此时只是处理了√n*√n的数组后面可能还有剩余。
划分好后通过Merge（）将前排序好的数组和目前需要排序的数组两两合并，需要操作√n次
代码： #include <stdio.h>#include <stdlib.h>#include <math.h>void Merge( int A[], int TmpA[], int L, int LeftEnd, int RightEnd ){ int R, NumElements, Tmp; int i; R=LeftEnd+1; Tmp = L; // 有序序列的起始位置 NumElements = RightEnd - L + 1; while( L <= LeftEnd && R <= RightEnd ) { if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++]; //将左边元素复制到TmpA else TmpA[Tmp++] = A[R++]; //将右边元素复制到TmpA } while( L <= LeftEnd ) TmpA[Tmp++] = A[L++]; // 直接复制左边剩下的 while( R <= RightEnd ) TmpA[Tmp++] = A[R++]; // 直接复制右边剩下的 for( i = 0; i < NumElements; i++, RightEnd -- ) A[RightEnd] = TmpA[RightEnd]; //将有序的TmpA[]复制回A[]}void RadicalSort(int Sarray[],int TmpA[],int low,int hight){ if(low<hight)//设置条件 { int tmp,i,j; tmp=(int)sqrt((double)(hight-low+1));//tmp为根号n for(i=0;i<tmp;i++) { RadicalSort(Sarray,TmpA,low+(i*tmp),low+((i+1)*tmp-1));//将数组分成tmp份 } if(low+tmp*tmp<=hight)//考虑到tmp*tmo后可能还有数组没有划分 { RadicalSort(Sarray,TmpA,low+tmp*tmp,hight); } for(j=1;j<tmp;j++)//对划分后的一个数组与前面所有划分过的排序 { Merge(Sarray,TmpA,low,(low+j*tmp)-1,(low+(j+1)*tmp)-1); } if(low+tmp*tmp<=hight) { Merge(Sarray,TmpA,low, low + tmp*tmp - 1, hight); } }}int main(){ srand(time( NULL )); int i,a; printf("根号分治n存入数组的大小"); scanf("%d",&a); int Sarray[a]; for(i=0;i<a;i++) { Sarray[i]=1 +(rand()%100); } printf("数组为n"); for(i=0;i<a;i++) printf("%dt",Sarray[i]); int *TmpA; TmpA = (int *)malloc(a*sizeof(int)); RadicalSort(Sarray,TmpA,0,a-1); free( TmpA ); printf("n数组n"); for(i=0;i<a;i++) printf("%dt",Sarray[i]);}