Sorting learning sorting

Merge sort

Recursive ：
Code ：

#include<iostream>
using namespace std;
const int maxn=100010;
int a[maxn];
void merge(int a[],int L1,int R1,int L2,int R2){
	int temp[maxn],index=0;// Zero time array temp, Used to store the sorted sequence ; 
	int i=L1;int j=L2;
	while(i<=R1&&j<=R2){//R2 For the initial n-1, No n, You can wait ; 
		if(a[i]<=a[j]){
			temp[index++]=a[i++];// Sort from small to large , Let the small one in first temp; 
		}else {
			temp[index++]=a[j++];
		}
	}
	while(i<=R1)temp[index++]=a[i++];// Because the length of the two sequences that may be merged is different , So the rest of the ratio is saved to temp Inside , The next step of recursion will continue to sort, so don't worry ; 
	while(j<=R2)temp[index++]=a[j++]; 
	for(int i=0;i<index;i++){
		a[L1+i]=temp[i];
	}
}
void mergesort(int a[],int left,int right){
	if(left<right){// Until there is only one element in each interval ; 
		int mid=left+(right-left)/2;
		mergesort(a,left,mid);
		mergesort(a,mid+1,right);
		merge(a,left,mid,mid+1,right);// There is one on every floor merge Merge ;
	}
}
int n;
int main(){
	cin>>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];
		if(i!=n-1)cout<<" ";
	}
	return 0;
}

Non recursive ( Shell Sort )：

#include<iostream>
using namespace std;
const int maxn=100010;
int a[maxn];
int main(){
	int n,j;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int step=n/2;step>0;step/=2){
		for(int i=step;i<n;i++){
			int temp=a[i];
			for(j=i-step;i>=0&&a[j]>temp;j-=step){
				a[j+step]=a[j];
			}
			a[j+step]=temp;
		}
	}
	for(int i=0;i<n;i++){
		cout<<a[i];
		if(i!=n-1)cout<<" ";
	} 
	return 0;
} 

The essence is to divide and conquer , It's all group sorting ;