Stable Merge Sort

This is a custom implementation of merge sort since .NET doesn't provide a stable sort algorithm. It falls back to insertion sort when the subarrays have at most 25 elements to reduce the generated garbage.

To use simply call MergeSort.Sort(array) for objects that implement IComparable<>, and MergeSort.Sort(array, comparerDelegate) for objects that don't.

using System;
using System.Collections.Generic;
 
namespace Engine
{
   /// <summary>
   /// Implementation of stable merge sort.
   /// </summary>
   class MergeSort
   {
      public static void Sort<T>(T[] entities) where T : IComparable<T>
      {
         if (entities.Length > 25)
         {
            int n = entities.Length / 2;
            T[] left = new T[n], right = new T[entities.Length - n];
            Array.Copy(entities, 0, left, 0, n);
            Array.Copy(entities, n, right, 0, entities.Length - n);
 
            Sort<T>(left);
            Sort<T>(right);
            Merge<T>(left, right, entities, DefaultComparer);
         }
         else
         {
            InsertionSort(entities, DefaultComparer);
         }
      }
 
      public static void Sort<T>(T[] entities, Comparison<T> comparer)
      {
         if (entities.Length > 25)
         {
            int n = entities.Length / 2;
            T[] left = new T[n], right = new T[entities.Length - n];
            Array.Copy(entities, 0, left, 0, n);
            Array.Copy(entities, n, right, 0, entities.Length - n);
 
            Sort<T>(left, comparer);
            Sort<T>(right, comparer);
            Merge<T>(left, right, entities, comparer);
         }
         else
         {
            InsertionSort(entities, comparer);
         }
      }
 
      private static void Merge<T>(T[] left, T[] right, T[] entities, Comparison<T> comparer)
      {
         int i = 0, j = 0, k = 0;
         int p = left.Length, q = right.Length;
         while (i < p && j < q)
         {
            int val = comparer(left[i], right[j]);
            if (val <= 0)
            {
               entities[k] = left[i];
               i++;
            }
            else
            {
               entities[k] = right[j];
               j++;
            }
            k++;
         }
         if (i == p)
            Array.Copy(right, j, entities, k, entities.Length - k);
         else
            Array.Copy(left, i, entities, k, entities.Length - k);
      }
 
      private static int DefaultComparer<T>(T left, T right) where T : IComparable<T>
      {
         return left.CompareTo(right);
      }
 
      private static void InsertionSort<T>(T[] array, Comparison<T> comparer)
      {
         for (int right = 1; right < array.Length; ++right)
         {
            for (int shift = right;
                 shift > 0 && comparer(array[shift], array[shift - 1]) < 0;
                 --shift)
            {
               T swap = array[shift];
               array[shift] = array[shift - 1];
               array[shift - 1] = swap;
            }
         }
      }
   }
}