arrays - 归并排序的最坏情况会在什么时候发生？

Question

我知道合并排序的最坏情况是 O(nlogn)，与平均情况相同。

但是，如果数据是升序或降序，这会导致最小比较次数，因此合并排序变得比随机数据更快。所以我的问题是:什么样的输入数据会产生导致合并排序变慢的最大比较数？

答案在 this问题说:

For some sorting algorithms (e.g. quicksort), the initial order of the elements can affect the number of operations to be done. However it doesn't make any change for mergesort as it will have to do exactly the same number of operations anyway: recursively divide into small arrays and then merge them back, in total Θ(nlogn) time.

然而这是错误的。此时我们有两个子数组，如果初始数据已排序，我们想合并它们，我们将只有 n/2 次比较。这是第一个子数组的所有元素，只有第二个数组的第一个元素。然而，我们可以实现的不止于此。我正在寻找该输入数据。

Answer 1

合并排序的最坏情况是合并排序必须执行最大数量的比较。

所以我将尝试以自下而上的方式构建最坏的情况:

1. 假设最后一步排序后的数组是{0,1,2,3,4,5,6,7}

2. 对于最坏的情况，此步骤之前的数组必须是 {0,2,4,6,1,3,5,7} 因为这里 left subarray={0 ,2,4,6} 和 right subarray={1,3,5,7} 将导致最大比较。(在左右子数组中存储备用元素)

   原因:数组的每个元素至少会被比较一次。

3. 在前面的步骤中对左右子数组应用相同的上述逻辑:对于数组 {0,2,4,6} 最坏的情况是如果前一个数组是 {0,4} 和 {2,6} 以及数组 {1,3,5,7} 最坏的情况是 {1,5} 和 {3,7}。

4. 现在对前面的步骤数组应用相同的方法: 对于最坏的情况:{0,4} 必须是 {4,0} , {2,6}必须是 {6,2} ,{1,5} 必须是 {5,1} {3,7} 必须是 {7,3} 。好吧，如果你看清楚了，这一步没有必要，因为如果集合/数组的大小为 2，那么即使大小为 2 的数组已排序，每个元素也至少会被比较一次。

现在自上而下分析情况

Applying Merge Sort using Divide and Conquer

Input array arr[] = [4,0,6,2,5,1,7,3]
                           /  \
                          /    \
                  [4,0,6,2] and [5,1,7,3]
                     / \           / \
                    /   \         /   \
                 [4,0] [6,2]    [5,1] [7,3]       Every pair of 2 will be compared atleast once therefore maximum comparison here
                   |     |        |     |
                   |     |        |     |
                 [0,4] [2,6]    [1,5] [3,7]      Maximum Comparison:Every pair of set is used in comparison     
                   \     /        \     /                        
                    \   /          \   /
                 [0,2,4,6]      [1,3,5,7]        Maximum comparison again: Every pair of set compared
                      \             /
                       \           / 
                     [0,1,2,3,4,5,6,7]          

现在您可以对任何大小为 n 的数组应用相同的逻辑

下面是实现上述逻辑的程序。

注意:以下程序仅对 2 的幂无效。这是为任何大小为 n 的数组提供最坏情况的通用方法。你可以自己尝试不同的数组输入。

class MergeWorstCase
{
    public static void print(int arr[])
    {
        System.out.println();
        for(int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
    public static void merge(int[] arr, int[] left, int[] right) {
        int i,j;
        for(i=0;i<left.length;i++)
                arr[i]=left[i];
        for(j=0;j<right.length;j++,i++)
                arr[i]=right[j];
    }

    //Pass a sorted array here
    public static void seperate(int[] arr) { 

            if(arr.length<=1)
                return;

            if(arr.length==2)
            {
                int swap=arr[0];
                arr[0]=arr[1];
                arr[1]=swap;
                return;
            }

        int i,j;
        int m = (arr.length + 1) / 2;
        int left[] = new int[m];
        int right[] = new int[arr.length-m];

        for(i=0,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in left subarray
            left[j]=arr[i];

        for(i=1,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in right subarray
            right[j]=arr[i];

        seperate(left);
        seperate(right);
        merge(arr, left, right);
    }
    public static void main(String args[])
    {
        int arr1[]={0,1,2,3,4,5,6,7};
        seperate(arr1);
        System.out.print("For array 1:");
        print(arr1);
        int arr2[]={0,1,2,3,4,5,6,7,8};
        seperate(arr2);
        System.out.print("For array 2:");
        print(arr2);            
    }
}

输出:

For array 1:
4 0 6 2 5 1 7 3 
For array 2:
8 0 4 6 2 5 1 7 3