迭代合并排序时间复杂度（自底向上）

Question

我在寻找时间复杂度方面遇到了问题。

• 首先，谈到MergeSort中的外部FOR，我认为重复是（1 Sumation（from i=1， to sizeOfArray）（2*i）=1 (2 4 8 16 32... size），但我也认为我错了。
• 我在测量内部FOR循环重复时也遇到了问题。

MergeSort（）{//迭代版本（自下而上）

            for(int currentSize = 1; currentSize < length; currentSize *= 2)        {
                for(int low = 0; low < length - currentSize; low += 2*currentSize){

                    int mid = low + currentSize - 1;
                    //min() is used here so if low is very close to the end of the array, high doesn't take outOfBoundries Value.
                    int high = Math.min(low + currentSize*2 -1, length - 1);

                }
            }

}

合并（int低，int中，int高）{

            // Copy both parts into the helper array
            for (int i = low; i <= high; i++) {
                    helper[i] = arrayForMergeSort[i];
            }

            int i = low;
            int j = middle + 1;
            int k = low;
            // Copy the smallest values from either the left or the right side back
            // to the original array
            while (i <= middle && j <= high) {
                    if (helper[i] <= helper[j]) {

                            arrayForMergeSort[k] = helper[i];
                            i++;
                    } else {

                            arrayForMergeSort[k] = helper[j];
                            j++;
                    }
                    k++;
            }
            // Copy the rest of the left side of the array into the target array
            while (i <= middle) {
                    arrayForMergeSort[k] = helper[i];
                    k++;
                    i++;
            }

    }

Answer 1

对于外循环，迭代次数为ceil（log2（长度））。

对于内部循环，每次迭代要合并的运行数是ceil（长度/电流大小）或地板（长度电流大小-1）/电流大小）。如果这是偶数，那么最后一次运行的大小可能小于电流大小。如果这是奇数，那么最后一次运行没有要合并的运行，也可能小于currrentSize。我不确定有没有办法计算合并操作的总数，而不使用迭代来求和每次迭代的合并操作。

在“生产”版本的合并排序中，一次性分配与原始数组大小相同（或1/2）的工作数组，然后，合并的方向（原始到工作或工作到原始）随每个外部循环而改变。如果程序预先计算外部迭代的次数，并且它是奇数，则可以进行预传递，以在初始传递上就地交换元素，从而进行偶数次合并传递，排序后的数据最终在原始数组中。