程序设计--归并排序

归并排序--分治（稳定的（就是说一个数组中有两个一样的数，当数组排序完后，两个数的位置不发生改变，那么我们就说他是稳定的））

快排是不稳定的，那么如何让快排稳定，就加入他的下标，这时候所有的值就不同了，那么就稳定了。

|--------left---|------right----|

1.找分界点，确定分界点mid，取左右两边的中间值mid=（l+r）/2

2.递归排序left，right

3.归并---合二为一（双路归并，合二为一）o（n）

时间复杂度是nlogn

双指针算法：
假设我们有两个有序的序列（最小值）

用两个指针分别指向序列的第一个值（最小值）

那么这时候比较这两个序列里面的最小值，就可以得到整个序列的最小值。

将最小值，依次放到后面，且该指针后移一位，重复以上过程。

#include<iostream>
using namespace std;
const int N=1e+6;

int n;
int q[N],temp[N];

void merge_sort(int q[],int l,int r){
    if(l>=r)return;
    
     int mid=(r+l)/2;
     
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    
    int m=0, i=l,j=mid+1;
   while(i<=mid&&j<=r){
       if(q[i]<q[j])temp[m++]=q[i++];
       else temp[m++]=q[j++];
   }
   while(i<=mid)temp[m++]=q[i++];
   while(j<=r)temp[m++]=q[j++];
   
   for(i=l,j=0;i<=r;i++,j++){
       q[i]=temp[j];
   }
    
}

int main(){
    
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    
    merge_sort(q,0,n-1);
    
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    
}