void merge(int array[], int low, int mid, int high)
{
        int i, k;
        int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申請空間，使其大小為兩個
//已經排序序列之和，該空間用來存放合并后的序列
        int begin1 = low;
        int end1 = mid;
        int begin2 = mid + 1;
        int end2 = high;
 
        for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)  //比較兩個指針所指向的元素，
//選擇相對小的元素放入到合并空間，并移動指針到下一位置
        { 
            if(array[begin1]<=array[begin2])
             {
              temp[k] = array[begin1++];
             }
            else
            {   
             temp[k] = array[begin2++];
            }
        }
        if(begin1 <= end1) //若第一個序列有剩余，直接拷貝出來粘到合并序列尾
        {
          memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
        }
        if(begin2 <= end2) //若第二個序列有剩余，直接拷貝出來粘到合并序列尾
        {
          memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
        }
        memcpy(array+low, temp, (high-low+1)*sizeof(int));//將排序好的序列拷貝回數組中
        free(temp);
}

void merge_sort(int array[], unsigned int first, unsigned int last)
{
        int mid = 0;
        if(first<last)
        {
                /*mid = (first+last)/2;*/ /*注意防止溢出*/
                /*mid = first/2 + last/2;*/
                mid = (first & last) + ((first ^ last) >> 1);
                merge_sort(array, first, mid);
                merge_sort(array, mid+1,last);
                merge(array,first,mid,last);
        }
}