#include<iostream>
#include <time.h>
using namespace std;
void merge(int*A, int p, int q, int r)
{
int i = 0;
int index1 = 0;
int index2 = 0;
int length1 = q - p + 1;
int length2 = r - q;
int* arr1=new int[length1+1];
int* arr2 = new int[length2+1];
for (i = 0; i < length1; i++)
{
arr1[i] = A[p - 1 + i];
}
for ( i = 0; i < length2; i++)
{
arr2[i] = A[q + i];
}
arr1[length1] = 100;
arr2[length2] = 100;
for (i =p-1;i<=r-1;i++)
{
if (arr1[index1]<arr2[index2])
{
A[i] = arr1[index1];
index1++;
}
else
{
A[i] = arr2[index2];
index2++;
}
}
delete[] arr1;
delete[] arr2;
}
void merge_sort(int* A, int p, int r)
{
int q;
if (p<r)
{
q = (p + r) / 2;
merge_sort(A, p, q);
merge_sort(A, q + 1, r);
merge(A, p, q, r);
}
}
int main()
{
srand((unsigned int)time(NULL));//设置当前时间为种子
int p[20];
for (size_t i = 0; i < 20; i++)
{
p[i] = rand() % 100 + 1;
}
merge_sort(p, 2, 17);
for (size_t i = 1; i < 16; i++)
{
cout << p[i] << " ";
}
system("pause");
}