#include <stdio.h>
#include <stdlib.h>
#define N 7
void merge(int arr[], int low, int mid, int high){
 int i, k;
 int *tmp = (int *)malloc((high-low+1)*sizeof(int));
 //申請(qǐng)空間，使其大小為兩個(gè)
 int left_low = low;
 int left_high = mid;
 int right_low = mid + 1;
 int right_high = high;
 for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比較兩個(gè)指針?biāo)赶虻脑?
  if(arr[left_low]<=arr[right_low]){
   tmp[k] = arr[left_low++];
  }else{
   tmp[k] = arr[right_low++];
  }
 }
 if(left_low <= left_high){ //若第一個(gè)序列有剩余，直接復(fù)制出來粘到合并序列尾
 //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
 for(i=left_low;i<=left_high;i++)
  tmp[k++] = arr[i];
 }
 if(right_low <= right_high){
 //若第二個(gè)序列有剩余，直接復(fù)制出來粘到合并序列尾
 //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
  for(i=right_low; i<=right_high; i++)
   tmp[k++] = arr[i];
 }
 for(i=0; i<high-low+1; i++)
  arr[low+i] = tmp[i];
 free(tmp);
 return;
}
void merge_sort(int arr[], 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(arr, first, mid);
  merge_sort(arr, mid+1,last);
  merge(arr,first,mid,last);
 }
 return;
}
int main(){
 int i;
 int a[N]={32,12,56,78,76,45,36};
 printf ("排序前 \n");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]);
 merge_sort(a,0,N-1); // 排序
 printf ("\n 排序后 \n");
 for(i=0;i<N;i++)
  printf("%d\t",a[i]); printf("\n");
 system("pause");
 return 0;
}