我知道mergesort的最坏情况是O（nlogn），与平均情况相同
但是，如果数据是升序或降序的，则会导致比较次数减少，因此mergesort比随机数据更快。所以我的问题是：什么样的输入数据会产生最大数量的比较，结果合并排序会变慢
这个问题的答案是：
对于某些排序算法（例如快速排序），排序的初始顺序为
元素会影响要执行的操作数。然而
不会对mergesort进行任何更改，因为它必须准确地进行更改
不管怎样，操作的数量是相同的：递归地划分为小的
数组，然后在总Θ（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}将导致最大的比较。（在左子数组和右子数组中存储备用元素）原因：数组的每个元素将至少比较一次
-
在前面的步骤中，对左、右子数组应用相同的上述逻辑：对于数组
{0,2,4,6}，最坏的情况是如果前一个数组是{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}。如果你看得很清楚，这一步是不必要的，因为如果集合/数组的大小是2，那么即使大小为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将至少进行一次比较，因此此处的最大比较
| | | |
| | | |
[0,4][2,6][1,5][3,7]最大比较：每对集合用于比较
\ / \ /
\ / \ /
[0,2,4,6][1,3,5,7]再次进行最大比较：每对集合进行比较
\ /
\ /
[0,1,2,3,4,5,6,7]
现在，您可以对任何大小为n的数组应用相同的逻辑
下面是实现上述逻辑的程序
注意：以下程序仅对2的幂无效。这是一种广义方法，可为任何大小为n的数组提供最坏情况。您可以自己尝试不同的数组进行输入。
类合并WorstCase
{
公共静态无效打印（int arr[]）
{
System.out.println（）；
对于（int i=0；i<；arr.length；i++）
系统输出打印（arr[i]+“”）；
System.out.println（）；
}
公共静态无效合并（int[]arr，int[]left，int[]right）{
int i，j；
对于（i=0；i<；left.length；i++）
arr[i]=左[i]；
对于（j=0；j<；right.length；j++，i++）
arr[i]=右[j]；
}
//在这里传递一个排序数组
公共静态无效分隔（int[]arr）{
如果（arr.length<；=1）
回来
如果（arr.length==2）
{
int swap=arr[0]；
arr[0]=arr[1]；
arr[1]=互换；
回来
}
int i，j；
int m=（arr.length+1）/2；
int left[]=新的int[m]；
右整数[]=新整数[arr.length-m]；
对于（i=0，j=0；i<；arr.length；i=i+2，j++）//在左子数组中存储替换元素
左[j]=arr[i]；
对于（i=1，j=0；i<；arr.length；i=i+2，j++）//在右侧子阵列中存储替换元素
右[j]=arr[i]；
分开（左）；
分离（右）；
合并（arr、左、右）；
}
公共静态void main（字符串参数[]）
{
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