22 归并排序

[zwkcoding]

归并排序

主要思想

分治思想，采用递归实现。 均匀划分，时间复杂度为 O(nlog n)

实现

void merge(int ll, int rr)  {
  // 把 a[ll..rr-1] 区间的数进行排序。 t 数组是临时存放有序的版本用的
  if(rr - ll <= 1) return ;
  int mid = ll + (rr -ll >> 1);
  merge(ll, mid);
  merge(mid, rr);
  int p = ll, q = mid, s = ll;
  while(s < rr)  {
    // || 是短路运算符，第一部分已经完全合并或者都没合并完但是前一个队首更大
    iif(p >= mid || (q < rr && a[p] > a[q]))  {
      t[s++] = a[q++];
      // ans += mid - p;   // 这里统计了逆序度对的个数
    } else  {
      t[s++] = a[p++];
    }
  }
}