Gegeven een reeks elementen vinden welke permutatie van deze elementen zou resulteren in het ergste geval van samenvoeging.
Asymptotisch samenvoegen sorteert altijd o (n log n) tijd, maar de gevallen die meer vergelijkingen vereisen, kosten in de praktijk over het algemeen meer tijd. We moeten in principe een permutatie vinden van input -elementen die zouden leiden tot maximaal aantal vergelijkingen wanneer gesorteerd met behulp van een typisch samenvoegingsalgoritme.

Voorbeeld:  

 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.   
 Hoe krijg je nu worst case input voor samenvoegen SORT voor een inputset?  
 
 Laten we proberen de array op de onderste manier te bouwen   
 Laat de gesorteerde array {12345678} zijn.  
 
 Om het slechtste geval van samenvoeging te genereren, zou de samenvoeging die resulteerde in een bovenstaande gesorteerde array zou moeten resulteren in maximale vergelijkingen. Om dit te doen, moet de linker- en rechter sub-array die betrokken is bij de samenvoegingsoperatie alternatieve elementen opslaan van gesorteerde array. d.w.z. linker sub-array moet {1357} zijn en de rechter sub-array moet {2468} zijn. Nu wordt elk eenmaal op het minst op het minste element vergeleken en dat zal resulteren in maximale vergelijkingen. We passen ook dezelfde logica toe voor linker en rechts sub-array. Voor array {1357} zal het slechtste geval zijn wanneer de linker en rechter sub-array respectievelijk {15} en {37} zijn en voor array {2468} Het slechtste geval zal plaatsvinden voor {24} en {68}.  
 
    Compleet algoritme -     
    GenerateWorStCase (arr [])       
 
 
 Maak twee hulparrays links en rechts en bewaar alternatieve array -elementen erin.  
 
 Bel GenerateWorStCase voor Left SubArray: GenerateWorStCase (links)  
 
 Bel GenerateWorStCase voor Right SubArray: GenerateWorStCase (rechts)  
 
 Kopieer alle elementen van linker- en rechter subarrays terug naar de originele array.  
 
 
 Hieronder is de implementatie van het idee  
 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>   
   
    Uitvoer:     
 
 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   
 Tijdcomplexiteit: O (n logn)   
 Hulpruimte: O (n)   
 REFERENTIES -    Stapel overloop