归并排序

归并排序最差运行时间是O(nlogn)，它是利用递归设计程序的典型例子。采用分治的思想。
归并排序的最基础的操作就是合并两个已经排好序的序列。
假设我们有一个没有排好序的序列，那么首先我们使用分割的办法将这个序列分割成一个一个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程如下：

                  1  4  3    5  2  6

                     /              

                 1,4,3           5,2,6

                  /                 /    

               1,4     3        5,2     6

　　　　/     /               /     /    

          1    4       3       5     2     6

　　　　/                     /        

          1,4         3          2,5       6

                 /                      

             1,3,4                    2,5,6

                            ||

 　　　　　　　　1,2,3,4,5,6

首先最核心的部分是如何合并两个有序列表：

void sort(int arr[], int first, int last) {
    int mid;
    if(first < last) {
        mid = (first + last)/2;
        sort(arr, first, mid);
        sort(arr, mid+1, last);
        merge(arr, first, mid, last);
    }
}

void merge(int arr[], int first, int mid, int last) {
    int temp[last-first +1];
    int i,j,k;
    for (i=first, j=mid +1, k=last; i<=mid, j<=last; k++) {
        if(arr[i] < arr[j]){
            temp[k] = arr[i];
            i++;
        } else 
        {
            temp[k] = arr[j];
            j++;
        }
        if(; i< mid+1; i++) {
            temp[k] = arr[i];
        }
        if(; j<last +1; j++){
            temp[k] = arr[j];
        }
    }
    for(i=first, i<=last; i++) {
        arr[i] = temp[i];
    }
}