归并排序

#include<bits/stdc++.h>

using namespace std;

void fun(int a[], int l, int m, int r){
	int i = l;
	int j = m + 1;  
	int k = 0;
	int t[10000];
	while(i <= m && j <= r){
		if(a[i] < a[j])
			t[k++] = a[i++];
		else 
			t[k++] = a[j++];
	}
	while( i <= m) t[k++] = a[i++];
	while( j <= r) t[k++] = a[j++];
	i = 0;
	while(i < k){
		a[l++] = t[i++]; 
	//	cout << t[i-1] << " "; //查看每次排序结果
	} 
//	cout << endl;
}


// 递归 
void sort(int a[], int l, int r){
	if(l < r){
		int m = (l + r) / 2;
		sort(a, l, m);
		sort(a, m+1, r);
		fun(a, l, m, r);
	}
	
}

//非递归 
void fsort(int a[], int l, int r){
	int s = 1;
	while(s <= r){
		l = 0;
		while(l <= r){
			
			int  p = l + s*2 - 1;//
			if(p > r) p = r; //防止越界                  
			int m = l + s - 1;// 分成 【l, m】 【m + 1 ， r】    例如 0 1 2 3 4 5 6 7第一次断点是 0 2 4 6 第二次 1 5  
			if(m > r) m = r;
			//int  m = (l + p) >> 1; 
	//		cout << l << " * " << m << " * " << p << " * " << s <<endl; 
			fun(a, l, m, p);
			l = p + 1;
		}
		s += s;
	}
	
}

void input(int a[], int n){
	int i = 0;
	while( i < n) cout << a[i ++] << " ";
	cout << endl;
}

int main(){
	int n = 8;
	int a[] = {49,38,65,67,76,13,27,28};
	
	
	sort(a,0,n - 1);
	cout << "递归: " ;
	input(a, n);
	
	
	fsort(a,0,n - 1);
	cout << "非递归: " ;
	input(a, n);
	  
	return 0;
}