#include<iostream>
#include<ctime>
#include<time.h>
#include<assert.h>
#include<cstdlib>
using namespace std;


//两两归并
void merge(int r[], int start, int mid, int end) {
	int i = start;//i,j,k均为工作指针
	int j = mid + 1;
	int k = start;
	int r1[10000] = { 0 };//确认r1的长度
	while (i <= mid && j <= end) {
		if (r[i] <= r[j])r1[k++] = r[i++];//r[i],r[j]较小者放入r1
		else r1[k++] = r[j++];
	}
	while (i <= mid)r1[k++] = r[i++];//收尾处理
	while (j <= end)r1[k++] = r[j++];
	for (int i = start;i <= end;i++) {//将r1复制回r
		r[i] = r1[i];
	}
}

//一趟二路归并
void mergePass(int r[], int length, int h) {//h为待归并有序表长
	int start = 1;
	int mid = start + h - 1;
	int end = start + 2 * h - 1;
	while (end <= length) {//正常归并情况
		merge(r, start, mid, end);
		start += 2 * h;//更新
		mid = start + h - 1;
		end = start + 2 * h - 1;
	}
	if (mid < length) {//剩余一个h，一个小于h的表的情况
		merge(r, start, mid, length);
	}
}

//归并排序
void mergeSort(int r[], int length) {
	int h = 1;
	while (h < length) {
		mergePass(r, length, h);
		h = 2 * h;
	}
}




int main() {

	srand(time(0));
	int data[10000];
	for (int i = 0;i < 10000;i++) {
		data[i] = rand();
	}
	//有范围rand()%(max-min+1)

	clock_t start, stop;//clock_t是clock（）返回的变量类型
	double duration;


	//测试归并排序
	start = clock();
	mergeSort(data, 10000);
	stop = clock();
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	cout << "归并排序运行时间为：" << duration << endl;
	return 0;

}