title: When will the worst case of Merge Sort occur?
body: <p>I know that worst case on mergesort is O(nlogn), the same as the average case.</p>
  
  <p>However, if the data are ascending or descending, this results to the <em>minimum number of comparisons</em>, and therefore mergesort becomes faster than random data. So my question is: What kind of input data produces the <em>maximum number of comparisons</em> that result to mergesort to be slower?</p>
  
  <p>The answer at <a href="https://stackoverflow.com/questions/23042184/how-to-make-a-worst-case-in-mergesort-in-c">this</a> question says:</p>
  
  <blockquote>
    <p>For some sorting algorithms (e.g. quicksort), the initial order of the
    elements can affect the number of operations to be done. However it
    doesn't make any change for mergesort as it will have to do exactly
    the same number of operations anyway: recursively divide into small
    arrays and then merge them back, in total Θ(nlogn) time.</p>
  </blockquote>
  
  <p>However this is wrong. At the point we have two subarrays and we want to merge them if the initial data are sorted we will have only n/2 comparisons. That is all the elements of the first subarray with <em>only</em> the first element of the second array. However we can achieve more than that. I'm looking for that input data.</p>