C++排序代码：归并排序

/*
归并排序：通过分块治理，现将分开的部分变得有序，再来进行合并。
排序稳定性：稳定
时间复杂度：O(N*logN)
空间复杂度：O(N)
*/

#include<iostream>
using namespace std;

int len = 8;  //元素个数
int a[8] = { 36,25,48,12,25,43,20,28 };  //给定待排数组
int b[8];  //归并排序需要准备同等大小的备用数组

void MergeSort(int l, int r) {
	if (l == r) {  //左指针等于右指针，直接返回
		return;
	}
	int mid = (l + r) >> 1;  //左右指针中间位置
	MergeSort(l, mid);  //先排序左边，不断递归
	MergeSort(mid + 1, r);  //排序右边
	int i = l;  //左指针 i 从左开始查看数据
	int j = mid + 1;  //右指针 j 从左开始查看数据
	int k = l;  //排序指针 k 从待排元素的第一个位置开始向右滑动
	while (i <= mid && j <= r) {  //如果两边都有元素
		if (a[i] < a[j]) {  //左边小的情况
			b[k] = a[i];
			i++;
		}
		else {  //右边小的情况
			b[k] = a[j];
			j++;
		}
		k++;
	}
	while (i <= mid) {  //左边有剩余元素
		b[k++] = a[i++];
	}
	while (j <= r) {  //右边有剩余元素，和上面只会执行一个
		b[k++] = a[j++];
	}
	for (i = l; i <= r; i++) {  //备用数组 b[] 拷贝到原数组 a[]
		a[i] = b[i];
	}
}

int main() {

	MergeSort(0, len - 1);

	//打印输出
	for (int i = 0; i < len - 1; i++) {
		cout << a[i] << " ";
	}
	cout << a[len - 1] << endl;

	return 0;
}