title: Merge sort variant: using link array
body: <p>I was looking for the variants of Merge Sort. So my textbook says, </p>
  
  <p><strong>A variant of function Merge in which No records need to be moved at all, can be implemented by use of an auxiliary array links.</strong></p>
  
  <p>Firstly, I would like to state the code. </p>
  
  <pre><code>Algo MergeSort(low,high)
  {
  
  // a is the array to be sorted using auxiliary array link. 
  
  if(high-low&lt;15)
  return InsertionSort1(a,link,low,high);
  
  else
  {
  
       mid = (low+high)/2;
      q=MergeSort(low,mid);
      r=MergeSort(mid+1,high);
      return Merge1(q,r);
  
  }
  
  }
  
  // The function Merge1 is as defined:
  
  function Merge1(q,r)
  {
  
  // q and r are pointers to list contained in the global array link[0:n], the lists pointed at by q //and r are merged and a pointer to the beginning of the merged list is returned.
  
      i=q;
      j=r;
      k=0;
  
  while(i!=0 &amp;&amp; j!=0) 
  { 
      if(a[i]&lt;=a[j])
      {
            link[k]=i;
            k=i;
            i=link[i];
      }
  
      else
      {
  
             link[k]=j;
             k=j;
             j=link[j];
      }
  } // end of while
  
  if(i=0) 
    link[k]=j;
  
  else
    link[k]=i;
  
  return link[0];
  }
  </code></pre>
  
  <p>Okay so what I understood of the algorithm is:</p>
  
  <ol>
  <li>If the number of elements are less than 15, apply insertion sort and sort those elements.</li>
  <li>This way, we will get many lists that will be sorted by themselves but the entire array will not be sorted as such. </li>
  <li>To sort the entire array, the function <code>Merge</code> is used. </li>
  </ol>
  
  <p>My question is, </p>
  
  <p><strong>How is the function <code>Merge</code> combining the different sorted lists to one sorted list? I dont have any idea of the concept of the <code>link</code> array.</strong></p>
  
  <p>I am sorry but I tried very hard to understand but I dont get how the output array is "sorted" ?</p>
  
  <p>Any kind of example will be of utmost help. 
  Thank You. </p>