#include <iostream>
#include "SortTestHelper.h"
#include <algorithm>
#include "Student.h"

using namespace std;

//将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void merge(T arr[], int l, int mid, int r) {
 T aux[r-l+1];
 for (int i=l; i<=r; i++) {
 aux[i-l] = arr[i];
 }

 int i = l, j=mid+1;
 for (int k=l; k<=r; k++) {
 if ( i > mid ) {
 arr[k]=aux[j-l];
 j++;
 }else if(j > r) {
 arr[k] = aux[i-l];
 i++;
 }else if(aux[i-l] < aux[j-l]) {
 arr[k] = aux[i-l];
 i++;
 }else{
 arr[k]=aux[j-l];
 j++; //此时并没有考虑数组越界的问题
 }
 }
}

//递归使用归并排序,对 arr[l....r)的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r) {

 if ( l >= r) //处理递归到底的情况
 return;

 int mid = (l+r)/2; //(当l或r)变得非常大的时候,对他们进行除法可能会产生溢出错误
 __mergeSort(arr, l, mid);
 __mergeSort(arr, mid+1, r);
 __merge(arr, l , mid ,r);
}

template<typename T>
void mergeSort(T arr[], int n) {

 __mergeSort(arr, 0, n-1);
}

int main() {
 // 先划分一半,再逐层向上排序
 //存储:空间复杂度较大 -> 需要用到更多的空间来存储归并排序的数据
 //使用三个索引,分别追踪不同归并序列的数据 i j k

 int n = 50000;

 cout << "Test for Random Array, size = " << n << ",random range [0, " << n << "]" << endl;
 int *arr1 = SortTestHelper::generateRandomArray(n,0,n);
 int *arr2 = SortTestHelper::copyIntArray(arr1,n);

 SortTestHelper::testSort("Insertion Sort" , insertSort, arr1, n);
 SortTestHelper::testSort("Merge Sort", mergeSort, arr2, n);

 delete[] arr1;
 delete[] arr2;

 return 0;
}