#include <stdio.h>
#include <stdlib.h>
void Merge (int arr[], int L, int M, int R)
{
/*此处数组的头指针和尾指针需要参数给出，便于获取数组长度*/
int LEFT_SIZE = M - L + 1; //M算作左序列一份子，左序列长度额外加一
int RIGHT_SIZE = R - M; //M不算右序列份子，右序列长度不需要加一
//分别新建数组存放左、右子序列
int L_arr[LEFT_SIZE];
int R_arr[RIGHT_SIZE];
//先原封不动将数组左、右两边分别copy到左、右子序列
for (int i = L; i <= M; i++) { //M是属于左序列的，所以要从L到M遍历
L_arr[i-L] = arr[i];
}
for (int j = M+1; j <= R; j++) { //M不属于右序列，所以从(M+1)遍历到R
R_arr[j-M-1] = arr[j];
}
//复制完毕后，同时操作左右子序列，排序、重构母序列
int i = 0; //左序列起始位置
int j = 0; //右序列起始位置
int k = L; //k作为母序列控制指针
//i,j都未到终点时，交替移动
//此处不等号不取等，就是因为数组长度与末位下标相差1
while (i < LEFT_SIZE && j < RIGHT_SIZE) {
if (L_arr[i] <= R_arr[j]) {
arr[k] = L_arr[i];
i++;
k++;
} else {
arr[k] = R_arr[j];
j++;
k++;
}
}
//若j先超过终点，将左边子序列后面剩余的数按顺序照搬到母序列
while (i < LEFT_SIZE) {
arr[k] = L_arr[i];
k++;
i++;
}
//若i先超过终点，将右边子序列后面剩余的数按顺序照搬到母序列
while (j < RIGHT_SIZE) {
arr[k] = R_arr[j];
k++;
j++;
}
}
void MergeSort (int arr[], int L, int R)
{
/*
为什么将分界点的计算放到MergeSort()里面而非其他位置？
1.Merge()是被MergeSort()调用的子函数，在MergeSort中算出M，以参数形式传给Merge()，更方便
2.避免了在main()中计算M的麻烦，保证了main()中只写主干程序
*/
/*
此处有巨坑，算出半长度后要记得加上左指针值，
另外要考虑整数除法其实是向下取整的，
要特别注意到最深处（每个子序列只有一个数）时，L,M,R的取值分别是多少，
以此确定[防止递归死循环的判定条件]应该怎么写，
可以举简单序列在纸上模拟运行到最后一步，观察L,M,R的特点，
本例中得出判定条件为 if (L > (R-1))
*/
int M = L + (R - L) / 2; //中点到底偏向哪边不重要，举简单例子观察就行
//递归调用函数必备，防死循环的条件判定
//一般来讲，最好通过观察实际用例来写，yy很容易出错
if (L > (R-1)) {
return;
} else {
MergeSort(arr, L, M);
MergeSort(arr, M+1, R);
Merge(arr, L, M, R);
}
}
int main ()
{
//输入待排序列的长度与内容
int n = 0;
int arr[100000];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d",&arr[i]);
}
//排序
MergeSort(arr, 0, n-1);
//输出结果
for (int i = 0; i < n; i++) {
printf("%d ",arr[i]);
}
return 0;
}
/*
补充：
1.测试用例一定要全面，长度为奇数和偶数的序列都要测试；
2.从0开始还是从1开始？在写的时候就要想好，等全部码完再查错很困难；
3.不等号到底要不要取等？用特殊样例测清楚再写；
4.如果从0开始管理数组，特别注意数组长度和末尾下标之间是相差1的；
*/
