For a given set of elements, determine which arrangement will result in the worst case scenario of merge sort?
We know that asymptotically, merge sort always takes O(n log n) time, but in practice, situations that require more comparisons usually take more time. Now we basically need to determine an arrangement of input elements that maximizes the number of comparisons when implementing a typical merge sort algorithm.
Example
Consider the following set of elements as a sorted array 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
The input array that results in the worst case scenario for merge sort is 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
We study how to construct the worst case scenario for merge sort Input collection?
Now we try to build the array in a bottom-up manner
Now let the sorted array be {11, 12, 13, 14, 15, 16, 17, 18}.
To construct the worst-case scenario for merge sort, the merge operation resulting in the above sorted array should result in the most comparisons. Therefore, the left subarray and right subarray participating in the merge operation should alternately store the elements of the sorted array. The left subarray should be {11, 13, 15, 17}, and the right subarray should be {12, 14, 16, 18 }. This way, each element of the array will be compared at least once, resulting in a maximum number of comparisons. Now we implement the same logic for the left sub-array and the right sub-array as well. For the array {11, 13, 15, 17}, the worst case occurs when its left subarray is {11, 15} and its right subarray is {13, 17}. For the array {12, 14, 16, 18}, The worst case occurs at {12, 14} and {16, 18}.
GenerateWorstCase(arr[])
Now we create two auxiliary arrays left and right, and Store alternating array elements in them.
We call GenerateWorstCase - GenerateWorstCase (left) on the left subarray
We call GenerateWorstCase on the right subarray - GenerateWorstCase (right)
Now we copy all the elements of the left and right subarrays back to the original array.
Demonstration
// C program to generate Worst Case of Merge Sort #include <stdlib.h> #include <stdio.h> // Indicates function to print an array void printArray(int A1[], int size1){ for (int i = 0; i < size1; i++) printf("%d ", A1[i]); printf("</p><p>"); } // Indicates function to join left and right subarray 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]; } // Indicates function to store alternate elemets in left // and right subarray 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]; } // Indicates function to generate Worst Case of Merge Sort int generateWorstCase(int arr1[], int l1, int r1){ if (l1 < r1){ int m1 = l1 + (r1 - l1) / 2; // creating two auxillary arrays int left1[m1 - l1 + 1]; int right1[r1 - m1]; // Storing alternate array elements in left // and right subarray split(arr1, left1, right1, l1, m1, r1); // Recursing first and second halves generateWorstCase(left1, l1, m1); generateWorstCase(right1, m1 + 1, r1); // joining left and right subarray join(arr1, left1, right1, l1, m1, r1); } } // Driver code int main(){ // Initializes sorted array 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 </p><p>"); printArray(arr1, n1); // generating worst Case of Merge Sort generateWorstCase(arr1, 0, n1 - 1); printf("</p><p>Input array that will result in " "worst case of merge sort is </p><p>"); 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
The above is the detailed content of Find the permutation that leads to the worst case scenario of merge sort in C. For more information, please follow other related articles on the PHP Chinese website!