Find the permutation that leads to the worst case scenario of merge sort in C

Concept

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

Method

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}.

Complete algorithm

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.

Example

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;
}

Output

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!