原理

  • 采用了分治的思想

  • 步骤

    • 将数列分为两部分，不要求相对大小问题
    • 对两部分进行递归处理
    • 合并两个子序列

      性质

  • 稳定性 ： 稳定的

  • 时间复杂度
    • 最优、平均、最坏复杂度均为归并排序 - 图1

      代码

      1. public void merge_sort(int[] a, int left, int right) {
      2. if (right - left + 1 <= 1) {
      3.    return;
      4. }
      5. int mid = left + (right - left) / 2;
      6. merge_sort(a, left, mid);
      7. merge_sort(a, mid + 1, right);
      8. int[] tmp = new int[right - left + 1];
      9. int l = left;
      10. int r = mid + 1;
      11. int num = 0;
      12. for (int i = 0; i < tmp.length && l <= mid && r <= right; i++) {
      13.    if (a[l] < a[r]) {
      14.        tmp[num++] = a[l++];
      15.    } else {
      16.        tmp[num++] = a[r++];
      17.    }
      18. }
      19. while (l <= mid) {
      20.    tmp[num++] = a[l++];
      21. }
      22. while (r <= right) {
      23.    tmp[num++] = a[r++];
      24. }
      25. for (int i = 0; i < tmp.length; i++) {
      26.    a[left + i] = tmp[i];
      27. }
      28. }