递归和非递归的合并排序算法在时空复杂度上有区别吗？

Question

我已经用divide and conquer方法实现了一个合并排序算法，其中一个数组被分割成两个子数组。

在我的代码中，我重新使用插入排序算法来对合并排序中的子数组进行排序。这种方法是正确的吗，还是我必须使用不同的排序方法来对合并排序中的子数组进行排序？

就对合并排序算法的理解而言，一切都很清楚，但在实现合并排序时，如何在不使用递归策略的情况下将一个数组划分为n个子数组。

递归或非递归是实现merge sort的有效方法吗？

下面是我在github上的代码片段。https:/github.comvamsikankipatialgorithms-in-javablobmastersrccomalgorithmssortMergeSort.java。

我从实现的角度理解了我的代码是错误的，因为我把数组只分成了两个子数组，而不是n个子数组。

需要任何帮助，从算法实现的角度来清楚理解合并排序。

下面是代码。

package com.algorithms.sort;

public class MergeSort {

    public static int[] increasing(int[] arr) {
        int[] result = new int[arr.length];
        int q = arr.length / 2;
        System.out.println("q: " + q);
        int[] left = new int[q];
        int[] right = new int[q];
        for (int i = 0; i < q; i++) {
            left[i] = arr[i];
        }
        int k = 0;
        for (int j = q; j < arr.length; j++) {
            right[k] = arr[j];
            k += 1;
        }
        left = InsertionSort.increasing(left);
        right = InsertionSort.increasing(right);

        // Printing
        for (int e : left) {
            System.out.print(e);
        }
        System.out.println("\n");
        for (int e : right) {
            System.out.print(e);
        }
        System.out.println("\n");

        int i = 0;
        int j = 0;
        int s = 0;
        while ((i < left.length) && (j < right.length)) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < left.length) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < right.length) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 1

比优化更重要的是，你必须首先实现正确性。有一个bug，在 increasing 静态方法：如果数组参数的大小不是偶数，则会在 right 子数组分配的大小不正确。int[] right = new int[q]; 应该是

int[] right = new int[arr.length - q];

此外，如果数组太小，你不应该尝试拆分。

在优化方面，你应该只回退到使用 InsertionSort() 当子阵列的大小低于阈值时，在16到128个元素之间。用不同的阈值和各种分布进行仔细的基准测试，将有助于为您的系统确定一个好的阈值。

按照目前的实现，你的函数的时间复杂度为 O(N)²) 因为它听从 InsertionSort 除最后一个合并阶段外，其他阶段都是如此。为了将复杂性降低到 O(N.log(N))你必须对子数组进行递归，直到它们的大小低于一个固定的阈值。

这里是一个修改的版本。

package com.algorithms.sort;

public class MergeSort {

    public static int threshold = 32;

    public static int[] increasing(int[] arr) {
        if (arr.length <= threshold)
            return InsertionSort.increasing(arr);

        int len1 = arr.length / 2;
        int[] left = new int[len1];
        for (int i = 0; i < len1; i++) {
            left[i] = arr[i];
        }
        int len2 = arr.length - len1;
        int[] right = new int[len2];
        for (int i = 0; i < len2; i++) {
            right[i] = arr[i + len1];
        }
        left = increasing(left);
        right = increasing(right);

        int[] result = new int[len1 + len2];
        int i = 0;
        int j = 0;
        int s = 0;
        while (i < len1 && j < len2) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < len1) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < len2) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 2

两者的时间复杂度都是O( n log n).

关于空间复杂度，在你的数据结构选择上的实现可能会有所不同.在递归中，如果你选择数组：空间复杂度。N log N如果你选择linked-list：空间复杂度是O(1)在迭代中：如果你选择数组：空间复杂度。N(根据你的实现，它是O( N log N)，因为你在每一个划分状态下都会创建一个新的子数组，为了将它降低到O(n)，你应该使用一个额外的数组作为原始数组的大小，以及索引)如果你选择linked-list：空间复杂度是O(1)

如你所见，linked-list最适合排序，除此之外，由于函数框架的创建，递归式可能会消耗比预期更多的内存，这取决于编程语言。

源代码