mergeSortBU(T arr[], int n)

Question

void mergeSortBU(T arr[], int n) {

   //  Merge Sort Bottom Up 无优化版本

    for( int sz = 1; sz < n ; sz += sz )

        for( int i = 0 ; i < n - sz ; i += sz+sz )

            // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并

            __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );

 老师__merge（）这个中间这个i+sz-1是怎么得出来的，中个这在merge中不是mid的只值吗

这个mid值可以不可以写成               (i+i+sz+sz-1)/2

Answer 1

qq_非攻_0 2021-12-14 11:33:44

我感觉是老师的讲法和一开始的动画演示不一致导致的理解误差。

动画演示是 一开始设size为2，那就对2个元素2个元素的进行排序，就是对2个length为1的数组归并。然后size扩大就4个、4个的排序，对2个length为2的数组归并。这时候归并的mid值就是size/2，也就是你写的（i+size-1）/2

老师的写法是一开始size为1，就直接对2个length为1的数组归并。size为2的时候 直接就归并4个。这时候归并的mid值就是size，也就是（i+size-1）。

我试了一下 按照动画演示大概是这样写的：

Answer 2

liuyubobobo 2021-01-07 07:11:23

从索引 i 开始，往后推 sz 个元素，他们的索引是从 i 到 i + sz - 1。

比如从索引 4 开始，往后推 6 个元素，他们的索引是：

4 5 6 7 8 9

9 = 4 + 6 - 1。

继续加油！：）

• qq_非攻_0 #1

  老师的写法是不是和动画演示不一致。
  动画演示的是 size等于2开始，然后对2个(size/2)的数组进行排序。
  老师的写法是 size等于1开始，然后对2个size的数组进行排序。
  确实理解了好久。截图是我按照动画演示理解写的：
  
      public <T extends Comparable> void sort(T[] arr, int length) {
          for (int size =2;size < length;size += size){
              for (int i = 0;((i+size-1)/2+1) < length ;i+=size){
                  // 归并 arr[i,(i+size-1)/2],arr[(i+size-1)/2+1.i+size-1]
                  merge(arr,i,(i+size-1)/2,Math.min(i+size-1,length-1));
              }
          }
      }