title: Issue with Merge Sort in C#
body: <p>As part of my plan to improve my programming skills, I have decided to attempt to sort a large array of strings lexicographically (which later on I plan to do so using threading). 
  I have researched different sorting algorithms and I have tried to implement a Merge Sort my self from what I understood. For now I plan to sort a few simple strings.</p>
  
  <p>I am inputting the following strings to be sorted in the below method:</p>
  
  <pre><code> string[] stringsArray = new string[] { "cixymn", "adfxij", "adxhxy", "abcdef", "iejfyq", "uqbzxo", "aaaaaa" };
   string[] stringSorted = MergeSort(stringsArray);
  
   // For display purposes
   foreach (string s in stringSorted)
          {
              Console.WriteLine("Item at index " + Array.IndexOf(stringSorted, s) + " is " + s);
          }
  </code></pre>
  
  <p>The result I am getting is the following:</p>
  
  <pre><code>Item at index 0 is aaaaaa
  Item at index 1 is abcdef
  Item at index 2 is adfxij
  Item at index 3 is uqbzxo
  Item at index 4 is 
  Item at index 4 is 
  Item at index 4 is 
  </code></pre>
  
  <p>Since to implement the merge sort, you must first divide the array into two, I can easily understand that in this case, the left part is being sorted successfully whereas the right part is being ignored.
  I am under the impression that this is happening because I am comparing the characters of each string from the left side of the array in every recursion (thus possibly ignoring the right). So I think I actually understood where the problem MIGHT be. However, I do not quite know how to go about this. Any help would be very greatly appreciated.</p>
  
  <p>Below is the code for the MergeSort method.</p>
  
  <pre><code>  private static string[] MergeSort(string[] stringsArray)
      {
          if (stringsArray.Length == 1)
          {
              return stringsArray;
          }
  
          int middle = stringsArray.Length / 2;
  
          string[] left = new string[middle];
          string[] right = new string[stringsArray.Length - middle];
  
          for (int i = 0; i &lt; middle; i++)
          {
              left[i] = stringsArray[i];
          }
  
          for (int i = 0; i &lt; stringsArray.Length - middle; i++)
          {
              right[i] = stringsArray[i + middle];
          }
  
          left = MergeSort(left);
          right = MergeSort(right);
  
          int leftPointer = 0;
          int rightPointer = 0;
  
          string[] sorted = new string[stringsArray.Length];
  
          for (int k = 0; k &lt; stringsArray.Length; k++)
          {
              if (k == left.Length)
              {
                  break;
              }
  
              for (int i = 0; i &lt; left[leftPointer].Count(); i++)
              {
                  var leftChar = left[leftPointer][i];
  
                  if (i == right[rightPointer].Count())
                  {
                      continue;
                  }
  
                  var rightChar = right[rightPointer][i];
  
                  if ((rightPointer == right.Length || leftPointer &lt; left.Length) &amp;&amp; leftChar &lt; rightChar)
                  {
                      sorted[k] = left[leftPointer];
                      sorted[k + 1] = right[rightPointer];
                      leftPointer++;
  
                      break;
                  }
  
                  if ((leftPointer == left.Length || rightPointer &lt; right.Length) &amp;&amp; (rightChar &lt; leftChar))
                  {
                      sorted[k] = right[rightPointer];
                      sorted[k + 1] = left[leftPointer];
                      rightPointer++;
                      break;
                  }
              }
          }
  </code></pre>
  
  <p>QUESTION #2 : How would you recommend optimizing the code in order to be able to use threading?</p>