#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> //用到了time函数
using namespace std;
/*
函数功能：实现已排序的两子数组有序合并
函数名：merge
参数：temp：中间数组，临时存放数据
a：待排序数组
left：待排序数组的左边界；right：右边界；middle：中间值
*/
void merge(int temp[],int a[],int left,int right,int middle)
{
int index1;
int index2;
int i,j,k;
for(i=left;i<=middle;i++)//将待排序数组的左半部分赋值给中间数组的左半部分
temp[i]=a[i];
for(j=1;j<=right-middle;j++)//将待排序数组的右半部分按照逆序方式赋值给中间数组的右半部分
temp[right-j+1]=a[middle+j];
for(index1=left,index2=right,k=left;k<=right;k++)//从中间的数组的做边界和右边界同时有序赋值给待排序数组，不用考虑数组边界问题
{
if(temp[index1]<temp[index2])
a[k]=temp[index1++];
else
a[k]=temp[index2--];
}
}
/*
函数功能：两路归并排序
函数名：merge
参数：d：中间数组，临时存放数据
s：待排序数组
left：待排序数组的左边界；right：右边界
*/
void mergesort(int d[],int s[],int left,int right)
{
if(left<right)
{
int mid=(left+right)/2;
mergesort(d,s,left,mid); //递归排序左半部分
mergesort(d,s,mid+1,right); //递归排序右半部分
merge(d,s,left,right,mid); //合并已排序好的左右两半部分
}
}
void stochastic()
{ 
	int i,d[50];
	srand((unsigned) time(NULL)); //用时间做钟，每次产生随机数不一样
for (i=0; i<50; i++)
{
	 d[i] = rand() % 101; //产生0-100的随机数
	printf("%d ",d[i]);
} 
  
}
int main()
{
	int i,d[50],s[50];
stochastic(); 
printf("\n");
for(i=0;i<50;i++)
printf("%d ",d[i]);
printf("\n");
for(i=0;i<50;i++)
printf("%d ",s[i]);
mergesort(d,s,0,50); //函数调用
for(int i = 0; i < 50; i++) //数组输出
cout << s[i] << endl;
getchar();
return 0;
}