归并排序

归并排序 (Merging Sort) 就是利用归并的思想实现的排序方法。

假设初始序列含有 n 个记录 ， 则可以看成是 n 个有序的子序列，每个子序列的长度为 1 ，然后两两归并，得到 [n/2] ([x]表示不小于 x 的最小整数)个长度为 2 或 1 的有序子序列；再两两归并，……，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法称为 2 路归并排序。

思路：将一个数组分成两部分（A,B）。
A实现左边有序，再实现右边有序，然后进行合并，最后实现A这一个大部分实现有序。
然后B同样进行以上同样的操作，最后B这一大部分实现有序，最后，AB合并，实现整体有序。 同样，在实现A的有序也是自底向上进行合并的。

public static void mergeSort(int array[],int first,int end,int temp[]){
    int mid = (first+end)/2;
    if(first < end){
        //左边有序
        mergeSort(array,first,mid,temp);
        //右边有序
        mergeSort(array,mid+1,end,temp);
        //进行合并
        merge(array,first,mid,end,temp);
    }
}

public static void merge(int array[],int first,int mid,int end,int temp[]){
    int index1=first,index2=mid+1;
    int k=first;
    for (int i = first; i < end+1; i++) {
        temp[i]=array[i];
    }
    while(true){
        if(index1==mid+1 && index2==end+1){
            break;
        }else{
            if(index1==mid+1){
                for(int n=index2;n<=end;n++){
                    array[k++]=temp[n];
                }
                break;
            }else if(index2==end+1){
                for(int n=index1;n<=mid;n++){
                    array[k++]=temp[n];
                }
                break;
            }else{
                if(temp[index1]<temp[index2]){
                    array[k++]=temp[index1++];
                }else{
                    array[k++]=temp[index2++];
                }
            }
        }
    }
}

复杂度分析

O(nlogn)

归并排序是一种比较占用内存，但却效率高且稳定的算法。

非递归实现归并排序

/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{
  int* TR = (int *)malloc(L->length * sizeof(int));  /* 申请额外空间 */
  int k = 1;
  while (k < L->length)
  {
    MergePass(L->r, TR, k, L->length);
    k = 2 * k;  /* 子序列长度加倍 */
    MergePass(TR, L->r, k, L->length);
    k = 2 * k;  /* 子序列长度加倍 */
  }
}

/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[], int TR[], int s, int t)
{
  int i = 1;
  int j;
  while (i <= n - 2 * s + 1)
  {
    Merge(SR, TR, i, i + s - 1, i + 2 * s - 1); /* 两两归并 */
    i = i + 2 * s;
  }
  if (i < n - s + 1) /* 归并最后两个序列 */
    Merge(SR, TR, i, i + s - 1, n);
  else               /* 若最后只剩下单个子序列 */
    for ( j = i; j <= n; j++)
      TR[j] = SR[j];
}