title: MergeSort Implementation in C#
body: <p>Currently studying algorithm analysis, and instead of blindly running off of pseudo-code from my textbook, I'm implementing each algorithm in C#. This is the psuedo-code:</p>
  
  <pre><code>MERGE-SORT(A,p,r)
  1  if p &lt; r
  2     q = (p+r)/2
  3     MERGE-SORT(A,p,q)
  4     MERGE-SORT(A,q+1,r)
  5     MERGE(A,p,q,r)
  
  MERGE(A,p,q,r)
  1  n1 = q - p + 1
  2  n2 = r - q
  3  let L[1..n1+1] and R[1..n2+1] be new arrays
  4  for i = 1 to n1
  5     L[i] = A[p+i-1]
  6  for j = 1 to n2
  7     R[j] = A[q+j]
  8  L[n1+1] = INF
  9  R[n1+1] = INF
  10 i = 1
  11 j = 1
  12 for k = p to r
  13    if L[i] &lt;= R[j]
  14       A[k] = L[i]
  15       i = i + 1
  16    else
  17       A[k] = R[j]
  18       j = j + 1
  </code></pre>
  
  <p>This is my code:</p>
  
  <pre><code>static void Main(string[] args)
  {
      int[] unsortedArray = new int[] { 5, 2, 7, 4, 1, 6, 8, 3, 9, 10 };
      MergeSort(ref unsortedArray, 1, unsortedArray.Length);
      foreach (int element in unsortedArray)
      {
          Console.WriteLine(element);
      }
      Console.Read();
  }
  
  private static void MergeSort(ref int[] unsortedArray, int leftIndex, int rightIndex)
  {
      if (leftIndex &lt; rightIndex)
      {
          int middleIndex = (leftIndex + rightIndex) / 2;
          //Sort left (will call Merge to produce a fully sorted left array)
          MergeSort(ref unsortedArray, leftIndex, middleIndex);
          //Sort right (will call Merge to produce a fully sorted right array)
          MergeSort(ref unsortedArray, middleIndex + 1, rightIndex);
          //Merge the sorted left &amp; right to finish off.
          Merge(ref unsortedArray, leftIndex, middleIndex, rightIndex);
      }
  }
  
  private static void Merge(ref int[] unsortedArray, int leftIndex, int middleIndex, int rightIndex)
  {
      int lengthLeft = middleIndex - leftIndex + 1;
      int lengthRight = rightIndex - middleIndex;
      int[] leftArray = new int[lengthLeft + 1];
      int[] rightArray = new int[lengthRight + 1];
      for (int i = 0; i &lt; lengthLeft; i++)
      {
          leftArray[i] = unsortedArray[leftIndex + i - 1];
      }
      for (int j = 0; j &lt; lengthRight; j++)
      {
          rightArray[j] = unsortedArray[middleIndex + j];
      }
      leftArray[lengthLeft] = Int32.MaxValue;
      rightArray[lengthRight] = Int32.MaxValue;
      int iIndex = 0;
      int jIndex = 0;
      for (int k = leftIndex; k &lt; rightIndex; k++)
      {
          if (leftArray[iIndex] &lt;= rightArray[jIndex])
          {
              unsortedArray[k] = leftArray[iIndex];
              iIndex++;
          }
          else
          {
              unsortedArray[k] = rightArray[jIndex];
              jIndex++;
          }
      }
  }
  </code></pre>
  
  <p>I'm not sure where I'm messing things up -- I tried to follow the pseudo-code as well as I could, but my output is funky (i.e. repeated values and not properly sorted).</p>
  
  <p>Debugging this didn't help me figure out the problem either (recursive solutions get too messy).</p>
  
  <p>Where am I going wrong, and how do I fix it? </p>