递归实现

merge函数利用的是双指针技巧降低复杂度。

mergeSort函数使用了递归，当中先对左右序列各调用一次mergeSort，再对整个序列调用merge。就按照最浅层的归并的思想去理解，不要大脑走到哪就step in。

另外mergeSort进入递归有个left<right的判定容易漏写。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 10;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;

LL Map[128];

void merge(int A[],int L1,int R1,int L2,int R2){
	
	int i=L1,j=L2;
	int temp[maxn];
	int index = 0;
	
	while(i<=R1&&j<=R2){//是≤不是＜ 
		if(A[i]<=A[j]){
			temp[index++] = A[i++];
		}else{
			temp[index++] = A[j++];
		}
	}
	
	while(i<=R1)temp[index++] = A[i++];//这个while很容易写成if 
	while(j<=R2)temp[index++] = A[j++];
	
	
	for(int i=0;i<index;i++){
		A[L1+i] = temp[i];
	}
	
}

void mergeSort(int A[],int l,int r){//递归实现的归并排序 
	if(l<r){
		int mid = (l+r)/2;
		mergeSort(A,l,mid);
		mergeSort(A,mid+1,r);
		merge(A,l,mid,mid+1,r); 
	}
	
} 



int main(){
	
	int A[maxn] = {66,12,33,57,64,27,39,66,78,66};
	
	mergeSort(A,0,maxn-1);

	for(int i=0;i<maxn;i++){
		printf("%d ",A[i]);
	}
	
	return 0;
}

非递归实现

基础的归并函数sort是一样的，但感觉非递归道理容易想明白但是实现起来细节多。注意两个for和一个if的<n不能写成<=n

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 10;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;

LL Map[128];

void merge(int A[],int L1,int R1,int L2,int R2){
	
	int i=L1,j=L2;
	int temp[maxn];
	int index = 0;
	
	while(i<=R1&&j<=R2){//是≤不是＜ 
		if(A[i]<=A[j]){
			temp[index++] = A[i++];
		}else{
			temp[index++] = A[j++];
		}
	}
	
	while(i<=R1)temp[index++] = A[i++];//这个while很容易写成if 
	while(j<=R2)temp[index++] = A[j++];
	
	
	for(int i=0;i<index;i++){
		A[L1+i] = temp[i];
	}
	
}

void mergeSort(int A[],int n){//非递归实现的归并排序 
	//step为组内元素个数(每归并一次乘二)
	for(int step=2;step/2<n;step*=2){
		//每step个元素一组，组内左一半step/2和右一半step/2的元素合并，注意有很多个这样的组
		for(int i=0;i<n;i+=step){
			int mid = i+step/2-1;//step/2为左子区间元素个数
			if(mid+1<n){//右子区间存在元素则合并 
				merge(A,i,mid,mid+1,min(i+step-1,n));
			}
		} 
	} 
	
} 



int main(){
	
	int A[maxn] = {66,12,33,57,64,27,39,66,78,66};
	
	mergeSort(A,maxn);

	for(int i=0;i<maxn;i++){
		printf("%d ",A[i]);
	}
	
	return 0;
}