title: Understanding merge sort optimization: avoiding copies
body: <p>I have below merge sort program in algorithms book, it is mentioned that The main problem is that merging two sorted lists requires linear extra memory, and the additional work spent copying to the temporary array and back, throughout the algorithm, has the effect of slowing down the sort considerably. This copying can be avoided by judiciously switching the roles of "a" and "tmp_array" at alternate levels of the recursion.</p>
  
  <p>My question is what does author mean "copying can be avoided by judiciously switching the roles of a and tmp_array at alternate levels of the recursion" and how it is possible in following code? Request to show an example how we can achieve this?</p>
  
  <pre><code>void mergesort( input_type a[], unsigned int n ) {
  
      input_type *tmp_array;
      tmp_array = (input_type *) malloc( (n+1) * sizeof (input_type) );
      m_sort( a, tmp_array, 1, n );
      free( tmp_array );
  }
  
  void m_sort( input_type a[], input_type tmp_array[ ], int left, int right ) {
  
      int center;
      if( left &lt; right ) {
  
      center = (left + right) / 2;
      m_sort( a, tmp_array, left, center );
      m_sort( a, tmp_array, center+1, right );
      merge( a, tmp_array, left, center+1, right );
      }
  }
  
  void merge( input_type a[ ], input_type tmp_array[ ], int l_pos, int r_pos, int right_end ) {
  
      int i, left_end, num_elements, tmp_pos;
      left_end = r_pos - 1;
      tmp_pos = l_pos;
      num_elements = right_end - l_pos + 1;
  
      /* main loop */
  
      while( ( 1_pos &lt;= left_end ) &amp;&amp; ( r_pos &lt;= right_end ) )
  
          if( a[1_pos] &lt;= a[r_pos] )
              tmp_array[tmp_pos++] = a[l_pos++];
          else
              tmp_array[tmp_pos++] = a[r_pos++];
  
      while( l_pos &lt;= left_end )  /* copy rest of first half */
          tmp_array[tmp_pos++] = a[l_pos++];
  
      while( r_pos &lt;= right_end ) /* copy rest of second half */
          tmp_array[tmp_pos++] = a[r_pos++];
  
      /* copy tmp_array back */
      for(i=1; i &lt;= num_elements; i++, right_end-- )
          a[right_end] = tmp_array[right_end];
  
  }
  </code></pre>