/*
 * 归并排序是稳定的 最好 最坏 平均情况时间复杂度都为O(log n) 空间复杂度为O(n) 在外排序中有着很好的应用。
 * 下面这个是递归的版本
*/
#include "iostream"
using namespace std;
void merge(int a[],int temp[],int left,int right,int rightEnd) { /* 合并2个有序的子序列 */
    int l = left;
    int leftEnd = right - 1;
    int len = rightEnd - left + 1;
    while (left <= leftEnd && right <= rightEnd) {
        if (a[left] <= a[right]) {
            temp[l] = a[left];
            left++;
        }
        else {
            temp[l] = a[right];
            right++;
        }
        l++;
    }
    while (left <= leftEnd)
        temp[l++] = a[left++];
    while (right <= rightEnd)
        temp[l++] = a[right++];
    /* 将temp中的元素复制回a数组 */
    for (int i = rightEnd; len>0; i--,len--) {
        a[i] = temp[i];
    }
}
void MSort(int a[],int temp[],int left,int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MSort(a, temp, left, mid);
        MSort(a, temp, mid + 1, right);
        merge(a, temp, left, mid + 1, right);
    }
}
void merge_sort(int a[],int n) {
    int* temp =  (int*)malloc(n*sizeof(int));
    if (temp != NULL) {
        MSort(a, temp, 0, n - 1);
        free(temp);
    }
    else {
        cout << "内存不足" << endl;
    }
}
void print(int  a[]) {
    for (int i = 0; i < 10; i++)
        cout << a[i] << " ";
    cout << endl;
}
int main() {
    int a[10] = { 3,5,7,4,2,1,0,8,9,6 };
    merge_sort(a, 10);
    print(a);
}

/*
 * 归并排序 最好 最坏 平均情况时间复杂度都为O(log n) 空间复杂度为O(n) 在外排序中有着很好的应用。
 * 下面这个是非递归的版本
*/
#include "iostream"
using namespace std;
void merge(int a[],int temp[],int left,int right,int rightEnd) { /* 合并2个有序的子序列 */
	int l = left;
	int leftEnd = right - 1;
	int len = rightEnd - left + 1;
	while (left <= leftEnd && right <= rightEnd) {
		if (a[left] <= a[right]) {
			temp[l] = a[left];
			left++;
		}
		else {
			temp[l] = a[right];
			right++;
		}
		l++;
	}
	while (left <= leftEnd)
		temp[l++] = a[left++];
	while (right <= rightEnd)
		temp[l++] = a[right++];
}
/* 一趟2路归并 */
void MergePass(int a[],int temp[],int n,int length) { /* length:当前有序子列的长度 */
	int i;
	for (i = 0; i <= n - 2 * length; i+=2*length) {
		merge(a,temp,i,i+length,i+2*length-1);
	}
	if (i + length < n)
		merge(a, temp, i, i + length, n - 1);
	else
		for (int j = i; j < n; j++)
			temp[j] = a[j];
}
void merge_sort(int a[],int n) {
	int* temp =  (int*)malloc(n*sizeof(int));
	int length = 1;
	if (temp != NULL) {
		while (length < n){
			MergePass(a, temp, n, length);
			length *= 2;
			MergePass(temp, a, n, length);
			length *= 2;
		}
		free(temp);
	}
	else {
		cout << "内存不足" << endl;
	}
}
void print(int  a[]) {
	for (int i = 0; i < 10; i++)
		cout << a[i] << " ";
	cout << endl;
}
int main() {
	int a[10] = { 3,5,7,4,2,1,0,8,9,6 };
	merge_sort(a, 10);
	print(a);
}