Update (9/6/2014) - Updated code on GitHub with performance enhancement to sorted merge algorithm.

As promised a few days ago, here’s the first installment in the algorithm series. A simple insertion sort and the previous sorted merge combine to provide you with a quick way to sort and merge multiple arrays without copying data from one array to another. You can find complete code and tests on GitHub.

Here’s the insertion sort code:

/// <summary>
/// Simple insertion sort of IList or array in place.
/// </summary>
/// <typeparam name="T">Type to be sorted.</typeparam>
/// <param name="data">IList or array to be sorted.</param>
public static void InsertionSort<T>(IList<T> data) 
   where T : IComparable
{
   if (data == null || data.Count < 2) return;
   for (int keyIndex = 1; keyIndex < data.Count; keyIndex++)
   {
      var key = data[keyIndex];
      var priorIndex = keyIndex - 1;
      while (priorIndex > -1 
         && data[priorIndex] != null 
         && data[priorIndex].CompareTo(key) > 0)
      {
         data[priorIndex + 1] = data[priorIndex];
         priorIndex -= 1;
      }
      data[priorIndex + 1] = key;
   }
}

And here’s one test example:

[TestMethod]
public void CombinedMergeSortTest()
{
   IList<MergeSortTestData> a = new List<MergeSortTestData> 
   { 
      new MergeSortTestData { Name = "Robert", Age = 43.5 },
      null,
   };
   IList<MergeSortTestData> b = new List<MergeSortTestData> 
   { 
      new MergeSortTestData { Name = "Robert", Age = 23.5 },
      null,
   };

   Sorter.InsertionSort(a);
   Sorter.InsertionSort(b);

   MergeSortTestData prev = null;
   int count = 0;
   foreach (var val in Merger.SortedMerge<MergeSortTestData>(a, b))
   {
      if (null != val) Assert.IsTrue(val.CompareTo(prev) > 0);
      prev = val;
      count++;
   }
   Assert.AreEqual(count, 4);
}


public class MergeSortTestData : IComparable
{
   public string Name { get; set; }
   public double Age { get; set; }

   public int CompareTo(object obj)
   {
      var other = obj as MergeSortTestData;
      if (null == other) return 1; //null is always less
      if (this.Name == other.Name)
      {
         return this.Age.CompareTo(other.Age);
      }
      return this.Name.CompareTo(other.Name);
   }
}