title: Merging in merge sort without using temporary arrays
body: <p>I'm trying to implement merge sort but somehow have been stuck for a day.</p>
  <p>[Sorry for pasting a big amount of code but wouldn't be able to do without it]</p>
  <p><strong>Implementation:</strong></p>
  <p><em>Merge Sort - Function</em></p>
  <pre><code>int mergeSort(int arr[], int low, int high)
  {
      int half = (low + high) / 2;    /* Find the middle element */ 
      if (low &lt; high) {
          if (high - low == 1)        /* If only one element, return */
              return;
          mergeSort(arr, low, half);  /* Sort First Half */
          mergeSort(arr, half, high); /* Sort Second Half */
          merge(arr, low, half, high); /* Merge */
      }
      return SUCCESS;
  }
  </code></pre>
  <p><em>Merging Step - Merge Function</em></p>
  <pre><code>int merge(int arr[], int low, int half, int high)
  {
      int i = 0, j = 0, k = 0, l = 0, temp;    /* Initialize indices */
  
      for (i = low, j = half; i &lt; half &amp;&amp; j &lt; high; i++, j++) { 
          /* Swap in the array itself if the elements are out of order */
          if (arr[i] &gt; arr[j]) {
              temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
  
      i = 0, j = low;  /* Compare and copy the elements in a global arrray C */
      for (k = 0; k &lt; SIZE &amp;&amp; i &lt; low &amp;&amp; j &lt; high; k++) {
          if (arr[i] &lt; arr[j]) {
              c[k] = arr[i];
              i++;
          } else {
              c[k] = arr[j];
              j++;
          }
      }
      
      if (i &lt; j) { /* Copy remaining elements to the end of the array C */
          for (l = i; l &lt; low; l++) {
              c[k++] = arr[l];
          }
      } else {
          for (l = j; l &lt; high; l++) {
              c[k++] = arr[l];
          }
      }
  </code></pre>
  <p><em>Output</em></p>
  <pre><code>8 --&gt; 9 --&gt; 
  4 --&gt; 5 --&gt; 8 --&gt; 9 --&gt; 
  4 --&gt; 5 --&gt; 8 --&gt; 9 --&gt; 
  1 --&gt; 2 --&gt; 4 --&gt; 5 --&gt; 8 --&gt; 9 --&gt; /* Sorting when left is sorted but right is in the process ? */
  4 --&gt; 5 --&gt; 6 --&gt; 7 --&gt; 8 --&gt; 9 --&gt; 1 --&gt; 2 --&gt; 
  1 --&gt; 2 --&gt; 4 --&gt; 5 --&gt; 6 --&gt; 7 --&gt; 8 --&gt; 9 --&gt; 
  1 --&gt; 2 --&gt; 6 --&gt; 7 --&gt; 4 --&gt; 5 --&gt; 8 --&gt; 9 --&gt; 
  
       
  </code></pre>
  <p><strong>Problem Description</strong></p>
  <p>I'm not using any local array for storing the elements of the array. Instead the elements are swapped if they are out of order and then copied into a global array by comparison
  Example: If I have the array</p>
  <pre><code>{ 9, 8, 4, 5, 2, 1, 7, 6 }
  </code></pre>
  <p>Then, firstly <code>{8,9}</code> would be sorted and then <code>{4,5}</code> would be sorted and then when copying procedure i.e <code>{8,4}</code> would be compared and so on.
  The following recursive calls take place</p>
  <pre><code>mergeSort(0,8) -&gt; mergeSort(0,4) , mergeSort(4,8), merge(0,4,8)
  mergeSort(0,4) -&gt; mergeSort(0,2) , mergeSort(2,4), merge(0,2,4)
  mergeSort(0,2) -&gt; 1 element calls
  and so on.
  </code></pre>
  <p>When merge is called when <code>{4,5,8,9}</code> are sorted , and the right is called <code>merge(4,5,6)</code> I have the following array</p>
  <pre><code>{4,5,8,9,1,2,7,6}
  </code></pre>
  <p>So, the algo tries to sort <code>{4,5,8,9}</code> and <code>{1,2}</code> when <code>{1,2}</code> is not a part of this subproblem i.e I want <code>{1,2}</code> and <code>'{6,7}</code> to become <code>{1,2,6,7}</code> and then combine both of these.</p>
  <p>How do I overcome this? I have been stuck for so many hours.</p>
  <p>Thanks a lot</p>