当将合并的最坏情况排序发生的呢？最坏、发生、情况
我知道，在归并最坏情况是O（nlogn），相同的情况下，平均
但是，如果数据被升序还是降序，这导致到比较的的最小数量，并且因此归并变得比随机数据更快。所以我的问题是：什么样的输入数据产生的比较的最大数量的是结果归并要慢一些。
在this问题说：
对于一些排序算法（例如快速排序）的初始订单 元件可以影响工作要做的操作次数。然而， 没有任何变化归并，因为它必须做完全 相同数量的操作呢：递归地划分成小 数组，然后将它们合并背后，总Θ（nlogn）的时间。
然而，这是错误的。在一点上，我们有两个子阵列，我们希望如果初始数据进行排序，我们将只有N / 2次比较合并它们。是第一子阵列的所有与元件的仅的所述第二阵列的第一个元素。然而，我们可以实现更多。我在寻找输入数据。
解决方案归并排序的最坏的情况将是一个在那里合并排序将不得不这样做比较最大数量。
因此，我将尝试建立最坏的情况下到上的方式：
排序后的 {0,1,2,3,4,5,6,7}
有关最坏的情况下在该步骤之前的数组必须是 {0,2,4,6,1,3,5,7} ，因为这里留下了子阵= {0,2,4,6} 和右子数组= {1,3,5,7} 将结果最大的比较。（中存储备用elemets左，右子数组的）
原因：数组的每一个元素都将被ATLEAST一次比较
。应用相同的上述逻辑，左，右子数组为previous步骤：对于数组 {0,2,4,6} 最坏的情况下将是如果previous数组是 {0,4} 和 {2,6} 和数组 {1,3,5,7} 最坏的情况将是 {1,5} 和 {3,7} 。
{0,4} 必须 {4,0} ， {2,6} 必须 {6,2} ， {1,5} 必须 {5,1} {3,7} 必须 {7,3} 。那么，如果你看清楚这步不需要，因为如果设置/数组的大小为2，则所有元素将被ATLEAST一次，即使大小为2的数组排序进行比较。
现在要自上而下和分析形势
应用归并排序使用分而治之
输入数组ARR [] = [4,0,6,2,5,1,7,3]
/ \
/ \
[4,0,6,2]及[5,1,7,3]
/ \ / \
/ \ / \
[4,0] [6,2] [5,1] [7,3]每对2将在这里进行比较ATLEAST一次，因此最大的比较
| | | |
| | | |
[0,4] [2,6] [1,5] [3,7]最大的比较：每对组是用在比较
\ / \ /
\ / \ /
[0,2,4,6] [1,3,5,7]再一次最大的比较：每对一套比较
\ /
\ /
[0,1,2,3,4,5,6,7]
现在，您可以采用同样的逻辑大小的任何阵列ñ
下面是实现了上述逻辑程序
注：以下程序不适用于仅2权力。它是一个广义的方法，以提供最坏的情况下为大小为n的任何阵列。你可以自己试试不同的阵列输入。的
类MergeWorstCase
{
公共静态无效打印（INT ARR []）
{
的System.out.println（）;
的for（int i = 0; I＆LT; arr.length;我++）
System.out.print（ARR [我] +）;
的System.out.println（）;
}
公共静态无效的合并（INT []改编，INT []离开，INT []右）{
INT I，J;
对于（i = 0; I＆LT; left.length;我++）
改编[i] =左[I]
为（J = 0; J＆LT; right.length; J ++，我++）
改编[i] =右[J]。
}
//传递一个排序的数组在这里
公共静态无效独立（INT [] ARR）{
如果（arr.length＆其中; = 1）
返回;
如果（arr.length == 2）
{
INT交换= ARR [0];
改编[0] =改编[1];
改编[1] =互换;
返回;
}
INT I，J;
INT米=（arr.length + 1）/ 2;
INT离开[] =新的INT [M]。
INT权[] =新的INT [arr.length-M]。
对于（i = 0，J = 0; I＆LT; arr.length; I = I + 2，J ++）//存储在左子数组替代元素
离开[J] =改编[I]
为（ⅰ= 1，J = 0; I＆其中; arr.length; I = I + 2，J ++）//存储在右子阵列替代元素
正确的研究[J] =改编[I]
单独的（左）;
独立（右）;
合并（ARR，左，右）;
}
公共静态无效的主要（字符串的args []）
{
INT ARR1 [] = {0,1,2,3,4,5,6,7};
独立（ARR1）;
System.out.print（对于数组1：）;
打印（ARR1）;
INT ARR2 [] = {0,1,2,3,4,5,6,7,8};
独立（ARR2）;
System.out.print（对于数组2：）;
打印（ARR2）;
}
}
输出：
对于数组1：
4 0 6 2 5 1 7 3
对于数组2：
8 0 4 6 2 5 1 7 3
I know that worst case on mergesort is O(nlogn), the same as the average case.
However, if the data are ascending or descending, this results to the minimum number of comparisons, and therefore mergesort becomes faster than random data. So my question is: What kind of input data produces the maximum number of comparisons that result to mergesort to be slower?
The answer at this question says:
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.
However this is wrong. At the point we have two subarrays and we want to merge them if the initial data are sorted we will have only n/2 comparisons. That is all the elements of the first subarray with only the first element of the second array. However we can achieve more than that. I'm looking for that input data.
解决方案The worst case of merge sort will be the one where merge sort will have to do maximum number of comparisons.
So I will try building the worst case in bottom up manner:
Suppose the array in final step after sorting is {0,1,2,3,4,5,6,7}
For worst case the array before this step must be {0,2,4,6,1,3,5,7} because here left subarray={0,2,4,6} and right subarray={1,3,5,7} will result in maximum comparisons.(Storing alternate elemets in left and right subarray)
Reason: Every element of array will be compared atleast once.
Applying the same above logic for left and right subarray for previous steps : For array {0,2,4,6} the worst case will be if the previous array is {0,4} and {2,6} and for array {1,3,5,7} the worst case will be for {1,5} and {3,7}.
{0,4} must be {4,0} , {2,6} must be {6,2} ,{1,5} must be {5,1} {3,7} must be {7,3} . Well if you look clearly this step is not necessary because if the size of set/array is 2 then every element will be compared atleast once even if array of size 2 is sorted.
Now going top down and analyzing the situation
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]
Now you can apply the same logic for any array of size n
Below is the program which implements the above logic.
Note:The below program isn't valid for powers of 2 only. It is a generalized method to provide the worst case for any array of size n. You can try different arrays for input by yourself.
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);
}
}
Output:
For array 1:
4 0 6 2 5 1 7 3
For array 2:
8 0 4 6 2 5 1 7 3
