[解決済み] Merge Sortの最悪のケースはどのような場合に発生するのでしょうか？

質問

マージソートのワーストケースはO(nlogn)であり、平均ケースと同じであることは知っています。

しかし、データが昇順または降順である場合、この結果は 比較の最小回数 従って、マージソートはランダムデータよりも高速になります。そこで質問ですが、どのような入力データであれば 比較の最大数 その結果、マージソートはより遅くなるのでしょうか？

での回答です。 これ の質問にはこうあります。

ある種のソートアルゴリズム（例：クイックソート）では、最初の順番が の要素は、行うべき操作の数に影響を与える可能性があります。しかし マージソートでは、まったく同じことをしなければならないので、何も変わりません。 どうせ同じ回数だけ、再帰的に分割して小さな 配列に結合し、それを再び結合するのにかかる時間は合計Θ(nlogn)です。

しかし、これは間違っています。2つの部分配列があり、それらをマージする場合、最初のデータがソートされていれば、n/2個の比較しかできません。つまり、最初の部分配列のすべての要素に のみ 2番目の配列の最初の要素。しかし、私たちはそれ以上のことを実現することができます。その入力データを探しているのです。

どのように解決するのですか？

マージソートの最悪のケースは、マージソートが以下のようなことをしなければならなくなることです。 比較の最大数。

そこで、ボトムアップ方式でワーストケースを構築してみることにします。

1. ソート後の最終段階の配列が {0,1,2,3,4,5,6,7}

2. 最悪の場合、このステップの前の配列は {0,2,4,6,1,3,5,7} というのも、ここでは左のサブアレイが {0,2,4,6} と右のサブアレイ {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