归并排序

基本概念

递归排序，分到很小再按序合并 - 稳定的 有特性为，当两个数等大，每次归并时，这两个数的前后顺序不变 - 时间复杂度 每步递归处理n个 $O(n)$，每次均分共递归 $lo{g}_2(n)$ 次 一共 $nlogn$

实现

 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 i = l, j = mid + 1, k = 0;  //用k来记录存下的数，只是更方便
 
     while(i <= mid && j <= r)
     {
   	  if(q[i] < q[j])
   		  t[k ++] = q[i ++];
   	  else
   		  t[k ++] = q[j ++];
     }
     while(i <= mid) t[k ++] = q[i ++];
     while(j <= r) t[k ++] = q[j ++];
 
     for(int i = l, j = 0; i <= r; i ++, j ++)
   	  q[i] = t[j];
 }