#include<bits/stdc++.h>
using namespace std;

const int A = 10010;                            				//常量 
int a[A] = {6,3,8,1,2,9,10,4,7,5};              				//芝士未排序的数组 
int temp[A];                                 			   		//芝士归并的临时数组  

void qs(int a[] , int b , int e)                				//快排 
{
	if(b == e) return;                        			  		//递归边界 
	
	int mid = a[b + e >> 1];                  			  		//任意取标准 
	int i = b - 1;                            			  		//指针一号从左往右 
	int j = e + 1;												//指针二号从右往左 
	
	while(i < j)                       			     	    	//只要一号没超过二号 
	{
		do i ++; while(a[i] < mid);        			    	 	//一号走一步 ， 要是大于标准就停 
		do j --; while(a[j] > mid);								//二号走一步 ， 要是小于标准就停 
		if(i < j) swap(a[i] , a[j]);       			   		  	//要是两个指针没交叉就交换 
	}
	
	qs(a , b , j);                             				 	//递归前半部分 
	qs(a , j + 1 , e);                        				  	//递归后半部分
}

void gb(int a[] , int b , int e)     							//归并 
{
	if(b >= e) return;											//递归边界 
	
	int mid = b + e >> 1;										//取中点 
	gb(a , b , mid);                           		 			//把前面排好 
	gb(a , mid + 1 , e);                        				//把后面排好          //这两步是递归 
	
	int cnt = 0;												//计数变量用于临时数组 
	int i = b;													//指针一号从头开始 
	int j = mid + 1;											//指针二号从中间开始  
	while(i <= mid and j <= e)                                  //只要都没到限制点 
	{
		if(a[i] <= a[j]) temp[cnt ++] = a[i ++];                //若一号向量小 ， 将其内容存入临时数组 ， 计数变量加一 
		else temp[cnt ++] = a[j ++];                            //若二号向量小 ， 将其内容存入临时数组 ， 计数变量加一 
	}
	while(i <= mid) temp[cnt ++] = a[i ++];                     //要是前半部分没存完 ， 把前半部分输入临时变量 （因为前面排序了所以是顺序的） 
	while(j <= e) temp[cnt ++] = a[j ++];                       //要是后半部分没存完 ， 把后半部分输入临时变量 （因为前面排序了所以是顺序的）
	
	for(i = b , j = 0 ; i <= e ; i ++ , j ++) a[i] = temp[j];   //将临时数组中的内容复制到a中 
}