title: Descending Mergesort
body: <p>I wrote some code to perform descending Merge Sort.</p>
  
  <pre><code>void Merge(int a[], int low, int high, int mid)
  {
  
  int i=low,j=mid+1,k=0;
  int temp[high-low+1];
  
  while(i&lt;=mid &amp;&amp; j&lt;= high)
  {
      if(a[i]&gt;a[j])               //comparison step
          temp[k++]=a[i++];
  
      else
          temp[k++]=a[j++];
  
  }
  
  while(i&lt;=mid)
      {
          temp[k++]=a[i++];
      }
  
  while(j&lt;=high)
      {
          temp[k++]=a[j++];
      }
  
  for(i=low;i&lt;=high;i++)
  {
  
      a[i]=temp[i-low];
  
  }
  
  
  return;
  }
  
  
  void MergeSort(int a[],int low, int high)
   {
  int mid;
  
  if(low&lt;high)
  {
      mid=(low+high)/2;
  
      MergeSort(a,low,mid);
      MergeSort(a,mid+1,high);
  
      Merge(a,low,high,mid);
  }
  
  return;
  }
  
  
  void output(int *a,int n)
  {
   for(int i=0;i&lt;n;i++)
   {
       cout&lt;&lt;a[i]&lt;&lt;"\t";
   }
  }
  
  int main()
  {
   int n=12;
   int a[n]={23,45,1,2,8,0,9,56,73,5070,20,16};
   MergeSort(a,0,n);
   output(a,n);
  
  }
  </code></pre>
  
  <p>This code works perfectly when the order is ascending, ie. comparsion is a[i] &lt; a[j] </p>
  
  <p>However by using a[j] > a[i] MergeSort beings sorting in descending order, but it will include some random large number right at the beginning of the array. I really can't figure out why this is happening. </p>