בהתחשב במערכת אלמנטים מוצאים אילו תמורה של אלמנטים אלה תביא למקרה הגרוע ביותר של מיזוג.
מיזוג אסימפטוטית מיזוג תמיד לוקח זמן (n log n), אך המקרים הדורשים השוואה רבה יותר בדרך כלל לוקח יותר זמן בפועל. בעיקרון עלינו למצוא פרמוטציה של אלמנטים קלט שיובילו למספר מקסימלי של השוואה כאשר הם ממוינים באמצעות אלגוריתם מיזוג טיפוסי.

דוּגמָה:  

 Consider the below set of elements    
 {1 2 3 4 5 6 7 8 9 10 11 12    
  13 14 15 16}   
  
 Below permutation of the set causes 153   
 comparisons.   
 {1 9 5 13 3 11 7 15 2 10 6    
  14 4 12 8 16}   
  
 And an already sorted permutation causes   
 30 comparisons.   
 עכשיו איך להשיג קלט במקרה הגרוע ביותר למיזוג מיזוג עבור מערך קלט?  
 
 מאפשר לנו לנסות לבנות את המערך בתחתית למעלה   
 תן למערך הממוין להיות {12345678}.  
 
 על מנת לייצר את המקרה הגרוע ביותר של מיזוג מיון, פעולת המיזוג שהביאה למערך ממוין לעיל אמורה לגרום להשוואה מקסימאלית. על מנת לעשות זאת, המערך המשנה השמאלי והימני המעורב בפעילות מיזוג צריך לאחסן אלמנטים חלופיים של מערך ממוין. כלומר, מערך המשנה השמאלי צריך להיות {1357} ומערך המשנה הימני צריך להיות {2468}. כעת ישווה כל אלמנט של מערך בפשטה אחת פעם אחת וזה יביא להשוואה מקסימאלית. אנו מיישמים גם את אותו היגיון על מערך משנה שמאל וימין. עבור מערך {1357} המקרה הגרוע ביותר יהיה כאשר מערך המשנה השמאלי והימני שלו הם {15} ו- {37} בהתאמה ולמערך {2468} המקרה הגרוע ביותר יתרחש עבור {24} ו- {68}.  
 
    אלגוריתם מלא -     
    Generateworstcase (arr [])       
 
 
 צור שני מערכי עזר שמאלה וימינה ואחסן בתוכם אלמנטים של מערך חלופי.  
 
 התקשרו ל- GenerateWorstCase עבור תת -מערך שמאלי: generateworstcase (משמאל)  
 
 התקשרו ל- GenerateWorstCase לקבלת מערך ימני: generateworstcase (מימין)  
 
 העתק את כל מרכיבי המשנה השמאלי והימני בחזרה למערך המקורי.  
 
 
 להלן יישום הרעיון  
 C++   
   // C++ program to generate Worst Case   // of Merge Sort   #include          using     namespace     std  ;   // Function to print an array   void     printArray  (  int     A  []     int     size  )   {      for  (  int     i     =     0  ;     i      <     size  ;     i  ++  )      {      cout      < <     A  [  i  ]      < <     ' '  ;      }      cout      < <     endl  ;   }   // Function to join left and right subarray   int     join  (  int     arr  []     int     left  []     int     right  []      int     l       int     m       int     r  )   {      int     i  ;      for  (  i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      arr  [  i  ]     =     left  [  i  ];      for  (  int     j     =     0  ;     j      <     r     -     m  ;     j  ++  )      {      arr  [  i     +     j  ]     =     right  [  j  ];      }   }   // Function to store alternate elements in   // left and right subarray   int     split  (  int     arr  []     int     left  []     int     right  []      int     l       int     m       int     r  )   {      for  (  int     i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      left  [  i  ]     =     arr  [  i     *     2  ];      for  (  int     i     =     0  ;     i      <     r     -     m  ;     i  ++  )      right  [  i  ]     =     arr  [  i     *     2     +     1  ];   }   // Function to generate Worst Case    // of Merge Sort   int     generateWorstCase  (  int     arr  []     int     l        int     r  )   {      if     (  l      <     r  )      {      int     m     =     l     +     (  r     -     l  )     /     2  ;      // Create two auxiliary arrays      int     left  [  m     -     l     +     1  ];      int     right  [  r     -     m  ];      // Store alternate array elements       // in left and right subarray      split  (  arr       left       right       l       m       r  );      // Recurse first and second halves      generateWorstCase  (  left       l       m  );      generateWorstCase  (  right       m     +     1       r  );      // Join left and right subarray      join  (  arr       left       right       l       m       r  );      }   }   // Driver code   int     main  ()   {          // Sorted array      int     arr  []     =     {     1       2       3       4       5       6       7       8       9        10       11       12       13       14       15       16     };          int     n     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);      cout      < <     'Sorted array is   n  '  ;      printArray  (  arr       n  );      // Generate Worst Case of Merge Sort      generateWorstCase  (  arr       0       n     -     1  );      cout      < <     '  n  Input array that will result '       < <     'in worst case of merge sort is   n  '  ;          printArray  (  arr       n  );      return     0  ;   }   // This code is contributed by Mayank Tyagi   
  C   
   // C program to generate Worst Case of Merge Sort    #include            #include            // Function to print an array    void     printArray  (  int     A  []     int     size  )      {         for     (  int     i     =     0  ;     i      <     size  ;     i  ++  )         printf  (  '%d '       A  [  i  ]);         printf  (  '  n  '  );      }      // Function to join left and right subarray    int     join  (  int     arr  []     int     left  []     int     right  []         int     l       int     m       int     r  )      {         int     i  ;     // Used in second loop       for     (  i     =     0  ;     i      <=     m     -     l  ;     i  ++  )         arr  [  i  ]     =     left  [  i  ];         for     (  int     j     =     0  ;     j      <     r     -     m  ;     j  ++  )         arr  [  i     +     j  ]     =     right  [  j  ];      }      // Function to store alternate elements in left    // and right subarray    int     split  (  int     arr  []     int     left  []     int     right  []         int     l       int     m       int     r  )      {         for     (  int     i     =     0  ;     i      <=     m     -     l  ;     i  ++  )         left  [  i  ]     =     arr  [  i     *     2  ];         for     (  int     i     =     0  ;     i      <     r     -     m  ;     i  ++  )         right  [  i  ]     =     arr  [  i     *     2     +     1  ];      }      // Function to generate Worst Case of Merge Sort    int     generateWorstCase  (  int     arr  []     int     l       int     r  )      {         if     (  l      <     r  )         {         int     m     =     l     +     (  r     -     l  )     /     2  ;         // create two auxiliary arrays       int     left  [  m     -     l     +     1  ];         int     right  [  r     -     m  ];         // Store alternate array elements in left       // and right subarray       split  (  arr       left       right       l       m       r  );         // Recurse first and second halves       generateWorstCase  (  left       l       m  );         generateWorstCase  (  right       m     +     1       r  );         // join left and right subarray       join  (  arr       left       right       l       m       r  );         }      }      // Driver code    int     main  ()      {         // Sorted array       int     arr  []     =     {     1       2       3       4       5       6       7       8       9           10       11       12       13       14       15       16     };         int     n     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);         printf  (  'Sorted array is   n  '  );         printArray  (  arr       n  );         // generate Worst Case of Merge Sort       generateWorstCase  (  arr       0       n     -     1  );         printf  (  '  n  Input array that will result in '      'worst case of merge sort is   n  '  );         printArray  (  arr       n  );         return     0  ;      }      
  Java   
   // Java program to generate Worst Case of Merge Sort   import     java.util.Arrays  ;   class   GFG      {      // Function to join left and right subarray      static     void     join  (  int     arr  []       int     left  []       int     right  []        int     l       int     m       int     r  )      {      int     i  ;      for     (  i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      arr  [  i  ]     =     left  [  i  ]  ;          for     (  int     j     =     0  ;     j      <     r     -     m  ;     j  ++  )      arr  [  i     +     j  ]     =     right  [  j  ]  ;      }          // Function to store alternate elements in left      // and right subarray      static     void     split  (  int     arr  []       int     left  []       int     right  []        int     l       int     m       int     r  )      {      for     (  int     i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      left  [  i  ]     =     arr  [  i     *     2  ]  ;          for     (  int     i     =     0  ;     i      <     r     -     m  ;     i  ++  )      right  [  i  ]     =     arr  [  i     *     2     +     1  ]  ;      }          // Function to generate Worst Case of Merge Sort      static     void     generateWorstCase  (  int     arr  []       int     l       int     r  )      {      if     (  l      <     r  )      {      int     m     =     l     +     (  r     -     l  )     /     2  ;          // create two auxiliary arrays      int  []     left     =     new     int  [  m     -     l     +     1  ]  ;      int  []     right     =     new     int  [  r     -     m  ]  ;          // Store alternate array elements in left      // and right subarray      split  (  arr       left       right       l       m       r  );          // Recurse first and second halves      generateWorstCase  (  left       l       m  );      generateWorstCase  (  right       m     +     1       r  );          // join left and right subarray      join  (  arr       left       right       l       m       r  );      }      }          // driver program      public     static     void     main     (  String  []     args  )         {      // sorted array      int     arr  []     =     {     1       2       3       4       5       6       7       8       9        10       11       12       13       14       15       16     };      int     n     =     arr  .  length  ;      System  .  out  .  println  (  'Sorted array is'  );      System  .  out  .  println  (  Arrays  .  toString  (  arr  ));          // generate Worst Case of Merge Sort      generateWorstCase  (  arr       0       n     -     1  );          System  .  out  .  println  (  'nInput array that will result in n'  +      'worst case of merge sort is n'  );          System  .  out  .  println  (  Arrays  .  toString  (  arr  ));      }   }   // Contributed by Pramod Kumar   
  Python   
   # Python program to generate Worst Case of Merge Sort   # Function to join left and right subarray   def   join  (  arr     left     right     l     m     r  ):   i   =   0  ;   for   i   in   range  (  m  -  l  +  1  ):   arr  [  i  ]   =   left  [  i  ];   i  +=  1  ;   for   j   in   range  (  r  -  m  ):   arr  [  i   +   j  ]   =   right  [  j  ];   # Function to store alternate elements in left   # and right subarray   def   split  (  arr     left     right     l     m     r  ):   for   i   in   range  (  m  -  l  +  1  ):   left  [  i  ]   =   arr  [  i   *   2  ];   for   i   in   range  (  r  -  m  ):   right  [  i  ]   =   arr  [  i   *   2   +   1  ];   # Function to generate Worst Case of Merge Sort   def   generateWorstCase  (  arr     l     r  ):   if   (  l    <   r  ):   m   =   l   +   (  r   -   l  )   //   2  ;   # create two auxiliary arrays   left   =   [  0   for   i   in   range  (  m   -   l   +   1  )];   right   =   [  0   for   i   in   range  (  r  -  m  )];   # Store alternate array elements in left   # and right subarray   split  (  arr     left     right     l     m     r  );   # Recurse first and second halves   generateWorstCase  (  left     l     m  );   generateWorstCase  (  right     m   +   1     r  );   # join left and right subarray   join  (  arr     left     right     l     m     r  );   # driver program   if   __name__   ==   '__main__'  :   # sorted array   arr   =   [  1     2     3     4     5     6     7     8     9     10     11     12     13     14     15     16  ];   n   =   len  (  arr  );   print  (  'Sorted array is'  );   print  (  arr  );   # generate Worst Case of Merge Sort   generateWorstCase  (  arr     0     n   -   1  );   print  (  '  n  Input array that will result in   n  '   +   'worst case of merge sort is '  );   print  (  arr  );   # This code contributed by shikhasingrajput    
  C#   
   // C# program to generate Worst Case of   // Merge Sort   using     System  ;   class     GFG     {          // Function to join left and right subarray      static     void     join  (  int     []  arr       int     []  left           int     []  right       int     l       int     m       int     r  )      {      int     i  ;      for     (  i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      arr  [  i  ]     =     left  [  i  ];      for     (  int     j     =     0  ;     j      <     r     -     m  ;     j  ++  )      arr  [  i     +     j  ]     =     right  [  j  ];      }      // Function to store alternate elements in      // left and right subarray      static     void     split  (  int     []  arr       int     []  left        int     []  right       int     l       int     m       int     r  )      {      for     (  int     i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      left  [  i  ]     =     arr  [  i     *     2  ];      for     (  int     i     =     0  ;     i      <     r     -     m  ;     i  ++  )      right  [  i  ]     =     arr  [  i     *     2     +     1  ];      }          // Function to generate Worst Case of       // Merge Sort      static     void     generateWorstCase  (  int     []  arr           int     l       int     r  )      {      if     (  l      <     r  )      {      int     m     =     l     +     (  r     -     l  )     /     2  ;      // create two auxiliary arrays      int  []     left     =     new     int  [  m     -     l     +     1  ];      int  []     right     =     new     int  [  r     -     m  ];      // Store alternate array elements      // in left and right subarray      split  (  arr       left       right       l       m       r  );      // Recurse first and second halves      generateWorstCase  (  left       l       m  );      generateWorstCase  (  right       m     +     1       r  );      // join left and right subarray      join  (  arr       left       right       l       m       r  );      }      }          // driver program      public     static     void     Main     ()         {          // sorted array      int     []  arr     =     {     1       2       3       4       5       6       7       8       9        10       11       12       13       14       15       16     };          int     n     =     arr  .  Length  ;      Console  .  Write  (  'Sorted array isn'  );          for  (  int     i     =     0  ;     i      <     n  ;     i  ++  )      Console  .  Write  (  arr  [  i  ]     +     ' '  );          // generate Worst Case of Merge Sort      generateWorstCase  (  arr       0       n     -     1  );      Console  .  Write  (  'nInput array that will '      +     'result in n worst case of'      +     ' merge sort is n'  );          for  (  int     i     =     0  ;     i      <     n  ;     i  ++  )      Console  .  Write  (  arr  [  i  ]     +     ' '  );      }   }   // This code is contributed by Smitha    
  JavaScript   
    <  script  >      // javascript program to generate Worst Case      // of Merge Sort      // Function to print an array      function     printArray  (  A    size  )      {      for  (  let     i     =     0  ;     i      <     size  ;     i  ++  )      {      document  .  write  (  A  [  i  ]     +     ' '  );      }      }      // Function to join left and right subarray      function     join  (  arr    left    right    l    m    r  )      {      let     i  ;      for  (  i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      arr  [  i  ]     =     left  [  i  ];      for  (  let     j     =     0  ;     j      <     r     -     m  ;     j  ++  )      {      arr  [  i     +     j  ]     =     right  [  j  ];      }      }      // Function to store alternate elements in      // left and right subarray      function     split  (  arr    left    right    l    m    r  )      {      for  (  let     i     =     0  ;     i      <=     m     -     l  ;     i  ++  )      left  [  i  ]     =     arr  [  i     *     2  ];      for  (  let     i     =     0  ;     i      <     r     -     m  ;     i  ++  )      right  [  i  ]     =     arr  [  i     *     2     +     1  ];      }      // Function to generate Worst Case      // of Merge Sort      function     generateWorstCase  (  arr    l    r  )      {      if     (  l      <     r  )      {      let     m     =     l     +     parseInt  ((  r     -     l  )     /     2       10  );      // Create two auxiliary arrays      let     left     =     new     Array  (  m     -     l     +     1  );      let     right     =     new     Array  (  r     -     m  );      left  .  fill  (  0  );      right  .  fill  (  0  );      // Store alternate array elements      // in left and right subarray      split  (  arr       left       right       l       m       r  );      // Recurse first and second halves      generateWorstCase  (  left       l       m  );      generateWorstCase  (  right       m     +     1       r  );      // Join left and right subarray      join  (  arr       left       right       l       m       r  );      }      }          let     arr     =     [  1       2       3       4       5       6       7       8       9        10       11       12       13       14       15       16     ];         let     n     =     arr  .  length  ;      document  .  write  (  'Sorted array is'     +     ' 
'  );      printArray  (  arr       n  );      // Generate Worst Case of Merge Sort      generateWorstCase  (  arr       0       n     -     1  );      document  .  write  (  ' 
'     +     'Input array that will result '      +     'in worst case of merge sort is'     +     ' 
'  );          printArray  (  arr       n  );          // This code is contributed by vaibhavrabadiya117.    <  /script>   
   
    תְפוּקָה:     
 
 Sorted array is    
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16    
  
 Input array that will result in worst    
 case of merge sort is    
 1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16   
 מורכבות זמן: o (n logn)   
 מרחב עזר: o (n)   
 הפניות -    ערימת הצפה