title: Merge Sort in R
body: <p>I am self studying the book <a href="http://mitpress.mit.edu/books/introduction-algorithms" rel="nofollow">"Introduction to Algorithms" by Cormen et alli.</a> In their book, they use pseudo-code which assumes that arrays are passed by pointer (by reference). This is different from R (where objects are passed by value), so I am having some difficulties trying to translate their pseudo-code as close as possible, especially when recursion is involved. Most of the time, I have to implement things a lot differently.</p>
  
  <p>For example, with the Merge Sort algorithm, they define the Merge Function (which I think I have translated correctly) and the recursive MergeSort function (where direct translation to R does not work).</p>
  
  <p>The merge function in pseudo-code is as follows where: A is an array and p, q, and r are indices into the array such that p &lt; q &lt; r. The procedure assumes that the subarrays A[p:q] and A[q+1:r] are in sorted order. It merges them to form a single sorted subarray that replaces the current subarray A[p:r]</p>
  
  <pre><code>Merge(A, p, q, r)
  n1 = q - p + 1
  n2 = r - q
  let L[1...n1+1] and R[1...n2+1] be new arrays
  for i = 1 to n1
      L[i] = A[p+i-1]
  for j = 1 to n2
      R[j] = A[q+j]
  L[n1+1] = infinite
  R[n2+1] = infinite
  i=1
  j=1
  for k = p to r
      if L[i] &lt;= R[j]
          A[j] = L[i]
          i = i + 1
      else
          A[k] = R[j]
          j = j + 1
  </code></pre>
  
  <p>Which I've translated to R as:</p>
  
  <pre><code>Merge &lt;- function(a, p, q, r){
    n1 &lt;- q - p + 1
    n2 &lt;- r - q
    L &lt;- numeric(n1+1)
    R &lt;- numeric(n2+1)
    for(i in 1:n1){
      L[i] &lt;- a[p+i-1]
    }
    for(j in 1:n2){
      R[j] &lt;- a[q+j]
    }
    L[n1+1] &lt;- Inf
    R[n2+1] &lt;- Inf
    i=1
    j=1
    for(k in p:r){
      if(L[i] &lt;= R[j]){
        a[k] &lt;- L[i]
        i &lt;- i +1
      }else{
        a[k] &lt;- R[j]
        j &lt;- j+1
      }
    }
    a
  }
  </code></pre>
  
  <p>And it seems to work fine.</p>
  
  <pre><code>Merge(c(1,3,5, 2,4,6), 1, 3, 6)
  [1] 1 2 3 4 5 6
  </code></pre>
  
  <p>Now the MergeSort function is defined in pseudo-code as follows:</p>
  
  <pre><code>MergeSort(A, p, r)
  if p &lt; r
     q = (p+r)/2
     MergeSort(A, p, q)
     MergeSort(A, q+1, r)
     Merge(A, p, q, r)
  </code></pre>
  
  <p>This assumes that A is passed by reference and that every change is visible to every recursive call, which is not true in R. </p>
  
  <p>So, <em>given the <code>Merge</code> function defined above</em>, how you would implement the <code>MergeSort</code> function in R to obtain the correct results? (if <strong>possible</strong>, and preferable, but not necessary, somewhat similar to the pseudo-code)</p>