数据结构-归并排序 （C++代码）

解题思路:

注意事项:

参考代码:

#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <cstring>
#include <string>

using namespace std;

void merge(int a[], int l, int mid, int r)
{
	int p1 = l, p2 = mid + 1, i = 0, len = r - l + 1;
	int *ax = new int[len]();
	while (p1 <= mid && p2 <= r)
		ax[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
	while (p1 <= mid) ax[i++] = a[p1++];
	while (p2 <= r) ax[i++] = a[p2++];
	for (i = 0; i < len; i++) a[l + i] = ax[i]; // 坑  "l + i"
	delete ax;
	return;
}

void mergeSort(int a[], int l, int r)
{
	if (l == r) return;
	int mid = l + ((r - l) >> 1);
	mergeSort(a, l, mid);
	mergeSort(a, mid + 1, r);
	merge(a, l, mid, r);
}

int main(void)
{
	int n = 0;
	cin >> n;
	int *a = new int[n]();
	for (int i = 0; i < n; i++)
		cin >> a[i];
	mergeSort(a, 0, n -1);
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	delete a;
	return 0;
}