归并排序

代码模板

void merge_sort(int q[],int l,int r)
{
    if(l>=r)return;//递归终止条件
    int mid=l+r>>1;//取中间值
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r); //递归分治 
    
    int cnt(0),i(l),j(mid+1);//cnt为tmp数组中的指针，i和j为需要归并的两个范围指针
    while(i<=mid&j<=r)
        if(q[i]<q[j]) tmp[cnt++]=q[i++];
        else tmp[cnt++]=q[j++];//指针对比，将更小的数值移入临时数组tmp当中
    while(i<=mid) tmp[cnt++]=q[i++];
    while(j<=r) tmp[cnt++]=q[j++];//确保所有数字全部被扫描，强制移动并填入数据
     
    for(i = l,j = 0;i<=r;i++,j++) q[i]=tmp[j];//由于是从第l个开始排序，所以i=l而不是=0}

代码原理

扫描

归并排序的本质是将一长段数据分为两个部分，然后通过两个指针一起从头开始对比，将更小的数字放入一个临时数组中，在数组一和数组二对比完毕以后，临时数组里面的数据理论上来说就是从小到大（或者按照需求改为从大到小）排好了。

​ 首先通过位运算划分中间点mid，其中以最小的数组为单位划分为A和B两个数组，这两个数组在分治的”最小单位“下理论上应该是从小到大依次分布的，只不过A、B两个数组相互独立。这个时候利用两个指针i和j对两个数组进行分别扫描，大致示意图如下

A 1 2 3 4 5 6 7
  ↑
  i
B 2 3 4 5 6 7 8
  ↑
  j
  
实际的数组: 1 2 3 4 5 6 7 2 3 4 5 6 7 8

填入临时数组

​ 定义一个临时数组tmp，在扫描的过程中，以上示例来说，由于A的1要比B的2更小，所以1被采用

，定义一个计数器cnt，将tmp[cnt++]定义为1(更小的数字)然后依次进行填充，直到两个数组都被扫描并且使用完毕

写入原数组

这个时候通过一个简单的for循环将排序好的tmp填入需要排序的q数组对应的位置即可。

时间复杂度

O(nlogn)