title: Generic Mergesort in C#
body: <p>I am trying to implement a generic <code>Mergesort</code> algorithm in <code>C#</code>, but I am having difficulty with the <code>Constraints</code>. I have searched many references but I can't find any that are implementing the algorithm like I am.</p>
  
  <p><a href="https://stackoverflow.com/questions/15835805/mergesort-algorithm-in-c-sharp">MergeSort algorithm in C#</a></p>
  
  <p><a href="http://blogsprajeesh.blogspot.com/2008/07/generic-implementation-of-sorting_17.html" rel="nofollow noreferrer">Generic Implementation of Sorting Algorithms</a></p>
  
  <p>Anyways, I am trying to provide an implementation that only allows the user to Mergesort a dataset that inherits from the <a href="http://msdn.microsoft.com/en-us/library/system.icomparable.aspx" rel="nofollow noreferrer"><code>IComparable</code></a> interface.</p>
  
  <p>Below is what I have so far:</p>
  
  <pre><code>using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Threading.Tasks;
  
  namespace SortUtil
  {
      class Program
      {
          static void Main(string[] args)
          {
              List&lt;int&gt; testList = new List&lt;int&gt; { 1, 5, 2, 7, 3, 9, 4, 6 };
              Mergesort.mergeSort&lt;int&gt;(testList); // Compiler Error at this Line.
          }
      }
      class Mergesort
      {   
          public static void mergeSort&lt;T&gt;(ref List&lt;T&gt; inputData)
              where T: IComparable&lt;T&gt;
          {
              mergeSort(ref inputData, 0, inputData.Count - 1);
          }
  
          private static void mergeSort&lt;T&gt;(ref List&lt;T&gt; inputData, int firstIndex, int lastIndex)
              where T: IComparable&lt;T&gt;
          {
              // If the firstIndex is greater than the lastIndex then the recursion 
              // has divided the problem into a single item. Return back up the call 
              // stack.
              if (firstIndex &gt;= lastIndex)
                  return;
  
              int midIndex = (firstIndex + lastIndex) / 2;
  
              // Recursively divide the first and second halves of the inputData into
              // its two seperate parts.
              mergeSort(ref inputData, firstIndex, midIndex);
              mergeSort(ref inputData, midIndex + 1, lastIndex);
  
              // Merge the two remaining halves after dividing them in half.
              merge(ref inputData, firstIndex, midIndex, lastIndex);
          }
  
          private static void merge&lt;T&gt;(ref List&lt;T&gt; inputData, int firstIndex, int midIndex, int lastIndex)
              where T: IComparable&lt;T&gt;
          {
              int currentLeft = firstIndex;
              int currentRight = midIndex + 1;
  
              T[] tempData = new T[(lastIndex - firstIndex) + 1];
              int tempPos = 0;
  
              // Check the items at the left most index of the two havles and compare
              // them. Add the items in ascending order into the tempData array.
              while (currentLeft &lt;= midIndex &amp;&amp; currentRight &lt;= lastIndex)
                  if (inputData.ElementAt(currentLeft).CompareTo(inputData.ElementAt(currentRight)) &lt; 0)
                  {
                      tempData[tempPos++] = inputData.ElementAt(currentLeft++);
                  }
                  else
                  {
                      tempData[tempPos++] = inputData.ElementAt(currentRight++);
                  }
  
              // If there are any remaining items to be added to the tempData array,
              // add them.
  
              while (currentLeft &lt;= midIndex)
              {
                  tempData[tempPos++] = inputData.ElementAt(currentLeft++);
              }
  
              while (currentRight &lt;= lastIndex)
              {
                  tempData[tempPos++] = inputData.ElementAt(currentRight++);
              }
  
              // Now that the items have been sorted, copy them back into the inputData
              // reference that was passed to this function.
              tempPos = 0;
              for (int i = firstIndex; i &lt;= lastIndex; i++) {
                  inputData.Insert(firstIndex, tempData.ElementAt(tempPos));
              }
          }
      }
  }
  </code></pre>
  
  <p><code>My issue:</code> I am getting a Compiler error in the Main method of the Program class; however, shouldn't I have to supply the <em>mergeSort</em> function the parametrized type when I call it statically? </p>
  
  <p>I am getting the error <code>"The best overloaded method match for... has some invalid arguments."</code></p>
  
  <p>I would greatly appreciate any implementation suggestions and/or any way of correcting this error. Note, I am most comfortable in Java, and since C# doesn't directly support wildcards this approach is foreign to me. Any explanations on this would be appreciated as well.</p>