#include "pch.h"
#include <iostream>
#include <vector>
using namespace std;

void merge(int* A, int left, int mid, int right)
{
	vector<int> B(right - left+1);
	int j = mid + 1;
	int k = 0;
	int i = left;
	while (i <= mid&&j <= right)
	{
		if (A[i] > A[j])
		{
			B[k++] = A[j];
			j++;
		}
		else
		{
			B[k++] = A[i++];
		}
	}
	while(j <= right)  //前面部分元素排列完毕，后面的就不用动了
	{
		B[k++] = A[j++];
	}
	while (i <= mid)  //后面的排完了，把前面的放到最后
	{
		B[k++] = A[i++];
	}
	/*for (int i = 0; i < right - left + 1; i++)
	{
		cout << B[i] << " ";
	}
	cout << endl;*/
	//这里之所以一直报错是因为left是动态的，那么for的判断条件也是动态了，所以就出错了
	//解决方法有二，一是用一个m来接受left然后做A的下标，二就是left+i
	/*int m = left;
	for (int i = 0; i < right-left+1; i++)
	{
		A[left++] = B[i];
	}*/
	for (int i = 0; i < right - left + 1; i++)
	{
		A[left+i] = B[i];
	}
}

void sort(int *A, int left, int right)  //这个函数是用来把一个数组层层扒开，然后变成一个一个的
{
	if(left < right)
	{
		int mid = (left+right)/2;
		sort(A, left, mid);
		sort(A, mid + 1, right);
		merge(A, left, mid, right);
	}
}

void mergeSort(int* A, int n)
{
	// write code here
	sort(A, 0, n - 1);
}

int main()
{
	int *arr = new int[13];
	arr[0] = 54;
	arr[1] = 35;
	arr[2] = 48;
	arr[3] = 36;
	arr[4] = 27;
	arr[5] = 12;
	arr[6] = 44;
	arr[7] = 44;
	arr[8] = 8;
	arr[9] = 14;
	arr[10] = 26;
	arr[11] = 17;
	arr[12] = 28;
	mergeSort(arr,13);
	for (int i = 0; i < 13; i++)
		cout << arr[i]<<" ";
	delete[]arr;
	return 0;
}