#include<cstdio>

void selection_sort(int arr[],int len)
{
	int minn,idx;
	
	for(int i=0;i<len;++i)
	{
		minn=2147483647;
		idx=i;
		
		for(int j=i;j<len;++j)
			if(arr[j]<minn)
			{
				minn=arr[j];
				idx=j;
			}
			
		int temp=arr[i];
		arr[i]=arr[idx];
		arr[idx]=temp;
	}
	
	//时间复杂度：O(n^2) 
	//空间复杂度：O(1) 
	//是否稳定：不稳定 
}

void bubble_sort(int arr[],int len)
{
	for(int i=0;i<len;++i)
		for(int j=0;j<i;++j)
			if(arr[i]>arr[i+1])
			{
				int temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
			
	//时间复杂度：O(n^2) 
	//空间复杂度：O(1) 
	//是否稳定：稳定 
}

void insertion_sort(int arr[],int len)
{
	int idx;
	
	for(int i=1;i<len;++i)
	{
		idx=i;
		
		while(arr[idx-1]>arr[idx])
		{
			int temp=arr[idx];
			arr[idx]=arr[idx-1];
			arr[idx-1]=temp;
			idx--;
		}
	}
	
	//时间复杂度：O(n^2) 
	//空间复杂度：O(1) 
	//是否稳定：稳定 
}

void quick_sort(int arr[],int left,int right)
{
	int i=left,j=right,flag=arr[left+(right-left)/2],temp;
	
	do
	{
		while(arr[i]<flag) i++;
		while(arr[j]>flag) j--;
		
		if(i<=j)
		{
			int temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
      i++;
      j--;
		}
	}
	while(i<=j);
	
	if(left<j) quick_sort(arr,left,j);
	if(right>i) quick_sort(arr,i,right);
	
	//时间复杂度：O(n log n) 
	//空间复杂度：O(log n) 
	//是否稳定：不稳定 
}

void merge_sort(int a[],int t[],int l,int r)
{
	if(l>=r)
		return;
		
	int mid=l+(r-l)/2;
	
	merge_sort(a,t,l,mid);
	merge_sort(a,t,mid+1,r);
	
	int i=l,p=l,q=mid+1;
	
	while(p<=mid && q<=r)
	{
		if(a[p]<=a[q])
			t[i++]=a[p++];
		else
			t[i++]=a[q++];
	}
	
	while(p<=mid)
		t[i++]=a[p++];
	while(q<=r)
		t[i++]=a[q++];
		
	for(int j=l;j<=r;++j)
		a[j]=t[j]; 
		
	//时间复杂度：O(n log n) 
	//空间复杂度：O(n) 
	//是否稳定：稳定 
}

int main()
{
	int a[]={6,5,4,3,2,1};
	int b[7]={};
	
	merge_sort(a,b,0,5);
	
	for(int i=0;i<6;++i)
		printf("%d ",a[i]); 
}