##http://c.biancheng.net/cpp/html/2742.html
//https://www.cnblogs.com/chengxiao/p/6194356.html
#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));
//申请空间，使其大小为两个
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++){ // 比较两个指针所指向的元素
if(arr[left_low]<=arr[right_low]){
tmp[k] = arr[left_low++];
}else{
tmp[k] = arr[right_low++];
}
}
if(left_low <= left_high){ //若第一个序列有剩余，直接复制出来粘到合并序列尾
//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){
//若第二个序列有剩余，直接复制出来粘到合并序列尾
//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){
//终止条件是，first=last,就是最有一个元素了，这个时候mid等于0吗
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;
}
