查找导致C语言中合并排序的最坏情况的排列
概念
对于给定的元素集，确定这些元素的哪些排列会导致合并排序的最坏情况？
渐近地，我们知道合并排序总是消耗O（nlogn）的时间，但是需要更多比较的情况在实践中通常会消耗更多的时间。现在，我们基本上需要确定输入元素的排列，当实施典型的合并排序算法进行排序时，这将导致最大数量的比较。
例
将以下元素集视为已排序数组11121314151617181920212223242526
将导致最坏的合并排序的结果输入数组是11191523132117251220162414221826
方法
我们研究如何为输入集的合并排序获取最坏情况的输入？
现在我们尝试以自底向上的方式构建数组
现在让排序后的数组为{11，12，13，14，14，15，16，17，18}。
现在，为了构建最坏的合并排序方法，导致上面排序的数组的合并操作应该产生最大的比较。结果，合并操作中涉及的左右子数组应存储sortedarray的备用元素，这样，左子数组应为{11，13，15，17}，右子数组应为{12，14，16，18}。因此，将比较数组的每个元素最少一次，这将导致最大的比较。现在，我们也为左右子数组实现了相同的逻辑。对于数组{11，13，15，17}，最坏的情况是当数组的左和右子数组分别为{11，15}和{13，17}且对于数组{12，14，16，18}最坏的情况将发生在{12，14}和{16，18}上。
完整算法
GenerateWorstCase（arr[]）
现在我们创建左右两个辅助数组，并在其中存储备用数组元素。
我们称左子数组为GenerateWorstCase-GenerateWorstCase（左）
我们将右侧子数组GenerateWorstCase称为GenerateWorstCase（右侧）
现在，我们将左右子数组的所有元素复制回原始数组。
示例
// C program to generate Worst Case of Merge Sort
#include <stdlib.h>
#include <stdio.h>
//表示打印数组的功能
void printArray(int A1[], int size1){
for (int i = 0; i < size1; i++)
printf("%d ", A1[i]);
printf("\n");
}
//指示连接左右子数组的功能
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
int i; // So used in second loop
for (i = 0; i <= m1 - l1; i++)
arr1[i] = left1[i];
for (int j = 0; j < r1 - m1; j++)
arr1[i + j] = right1[j];
}
//指示用于在左侧存储备用要素的功能
//和正确的子数组
int split(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
for (int i = 0; i <= m1 - l1; i++)
left1[i] = arr1[i * 2];
for (int i = 0; i < r1 - m1; i++)
right1[i] = arr1[i * 2 + 1];
}
//指示用于生成最坏情况的合并排序的功能
int generateWorstCase(int arr1[], int l1, int r1){
if (l1 < r1){
int m1 = l1 + (r1 - l1) / 2;
//创建两个辅助数组
int left1[m1 - l1 + 1];
int right1[r1 - m1];
//在左侧存储备用数组元素
//和正确的子数组
split(arr1, left1, right1, l1, m1, r1);
//递归前半部分和后半部分
generateWorstCase(left1, l1, m1);
generateWorstCase(right1, m1 + 1, r1);
// joining left和正确的子数组
join(arr1, left1, right1, l1, m1, r1);
}
}
//驱动程式码
int main(){
//初始化排序数组
int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
printf("Sorted array is \n");
printArray(arr1, n1);
//生成合并排序的最坏情况
generateWorstCase(arr1, 0, n1 - 1);
printf("\nInput array that will result in " "worst case of merge sort is \n");
printArray(arr1, n1);
return 0;
}输出结果
Sorted array is 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Input array that will result in worst case of merge sort is 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26