.gitignore

/obj
/bin
*.suo
*.user

AssemblyInfo.cs

using System.Reflection;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

// アセンブリに関する一般情報は以下の属性セットをとおして制御されます。
// アセンブリに関連付けられている情報を変更するには、
// これらの属性値を変更してください。
[assembly: AssemblyTitle("TrimSort")]
[assembly: AssemblyDescription("")]
[assembly: AssemblyConfiguration("")]
[assembly: AssemblyCompany("")]
[assembly: AssemblyProduct("TrimSort")]
[assembly: AssemblyCopyright("Copyright ©  2011")]
[assembly: AssemblyTrademark("")]
[assembly: AssemblyCulture("")]

// ComVisible を false に設定すると、その型はこのアセンブリ内で COM コンポーネントから 
// 参照不可能になります。COM からこのアセンブリ内の型にアクセスする場合は、
// その型の ComVisible 属性を true に設定してください。
[assembly: ComVisible(false)]

// 次の GUID は、このプロジェクトが COM に公開される場合の、typelib の ID です
[assembly: Guid("d2588ecc-1c11-467d-83b6-8159202720fd")]

// アセンブリのバージョン情報は、以下の 4 つの値で構成されています:
//
//      Major Version
//      Minor Version 
//      Build Number
//      Revision
//
// すべての値を指定するか、下のように '*' を使ってビルドおよびリビジョン番号を 
// 既定値にすることができます:
// [assembly: AssemblyVersion("1.0.*")]
[assembly: AssemblyVersion("1.0.0.0")]
[assembly: AssemblyFileVersion("1.0.0.0")]

Comparers.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TrimSort
{
    public static class Comparers
    {
        public class ComparerInt : Comparer<int>
        {
            public override int Compare(int x, int y)
            {
                return x - y;
            }
        }
        public class ComparerString : StringComparer
        {
            public override int Compare(string x, string y)
            {
                return String.Compare(x, y);
            }

            public override bool Equals(string x, string y)
            {
                return x == y;
            }

            public override int GetHashCode(string obj)
            {
                return obj.GetHashCode();
            }
        }
    }
}

TimSort.cs

//NOTICE!! this class is not tested enough.
/*
 * Copyright 2009 Google Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace TimSort
{
    /// <summary>
    /// A stable, adaptive, iterative mergesort that requires far fewer than
    /// n lg(n) comparisons when running on partially sorted arrays, while
    /// offering performance comparable to a traditional mergesort when run
    /// on random arrays.  Like all proper mergesorts, this sort is stable and
    /// runs O(n log n) time (worst case).  In the worst case, this sort requires
    /// temporary storage space for n/2 object references; in the best case,
    /// it requires only a small constant amount of space.
    /// 
    /// This implementation was adapted from Tim Peters's list sort for
    /// Python, which is described in detail here:
    /// 
    ///   http://svn.python.org/projects/python/trunk/Objects/listsort.txt
    /// 
    /// Tim's C code may be found here:
    /// 
    ///   http://svn.python.org/projects/python/trunk/Objects/listobject.c
    /// 
    /// The underlying techniques are described in this paper (and may have
    /// even earlier origins):
    /// 
    ///  "Optimistic Sorting and Information Theoretic Complexity"
    ///  Peter McIlroy
    ///  SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
    ///  pp 467-474, Austin, Texas, 25-27 January 1993.
    /// 
    /// While the API to this class consists solely of static methods, it is
    /// (privately) instantiable; a TimSort instance holds the state of an ongoing
    /// sort, assuming the input array is large enough to warrant the full-blown
    /// TimSort. Small arrays are sorted in place, using a binary insertion sort.
    /// @author Josh Bloch
    /// 
    /// This class is converted from following class.
    /// http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
    /// </summary>
    /// <typeparam name="T">sort type</typeparam>
    public class TimSort<T> //: IEnumerable<T>
    {
        /// <summary>
        /// This is the minimum sized sequence that will be merged.  Shorter
        /// sequences will be lengthened by calling binarySort.  If the entire
        /// array is less than this length, no merges will be performed.
        /// 
        /// This constant should be a power of two.  It was 64 in Tim Peter's C
        /// implementation, but 32 was empirically determined to work better in
        /// this implementation.  In the unlikely event that you set this constant
        /// to be a number that's not a power of two, you'll need to change the
        /// <seealso cref="minRunLength"/> computation.
        /// 
        /// If you decrease this constant, you must change the stackLen
        /// computation in the TimSort constructor, or you risk an
        /// ArrayOutOfBounds exception.  See listsort.txt for a discussion
        /// of the minimum stack length required as a function of the length
        /// of the array being sorted and the minimum merge sequence length.
        /// </summary>
        private const int MIN_MERGE = 32;
        /// <summary>
        /// The array being sorted.
        /// </summary>
        private T[] a;
        /// <summary>
        /// The comparator for this sort.
        /// </summary>
        private IComparer<T> c;

        /// <summary>
        /// When we get into galloping mode, we stay there until both runs win less
        /// often than MIN_GALLOP consecutive times.
        /// </summary>
        private const int MIN_GALLOP = 7;
        /// <summary>
        /// This controls when we get *into* galloping mode.  
        /// It is initialized to MIN_GALLOP.  The mergeLo and
        /// mergeHi methods nudge it higher for random data,
        /// and lower for highly structured data.
        /// </summary>
        private int minGallop = MIN_GALLOP;
        /// <summary>
        /// Maximum initial size of tmp array, which is used for
        /// merging.  The array can grow to accommodate demand.
        /// Unlike Tim's original C version, we do not allocate 
        /// this much storage when sorting smaller arrays.
        /// This change was required for performance.
        /// </summary>
        private const int INITIAL_TMP_STORAGE_LENGTH = 256;
        /// <summary>
        /// Temp storage for merges.
        /// </summary>
        private T[] tmp; // Actual runtime type will be Object[], regardless of T

         /**
         * A stack of pending runs yet to be merged.  Run i starts at
         * address base[i] and extends for len[i] elements.  It's always
         * true (so long as the indices are in bounds) that:
         *
         *     runBase[i] + runLen[i] == runBase[i + 1]
         *
         * so we could cut the storage for this, but it's a minor amount,
         * and keeping all the info explicit simplifies the code.
         */
        /// <summary>
        /// Number of pending runs on stack
        /// </summary>
        private int stackSize = 0;
        private int[] runBase;
        private int[] runLen;
        /// <summary>
        /// Creates a TimSort instance to maintain the state of an ongoing sort.
        /// </summary>
        /// <param name="a">the array to be sorted</param>
        /// <param name="c">the comparator to determine the order of the sort</param>
        private TimSort(T[] a, IComparer<T> c) 
        {
            this.a = a;
            this.c = c;

            // Allocate temp storage (which may be increased later if necessary)
            var len = a.Length;
            //@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
            var newArray = (T[]) new T[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
                                            len >> 1 : INITIAL_TMP_STORAGE_LENGTH];
                                            //len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
            tmp = newArray;

            /*
             * Allocate runs-to-be-merged stack (which cannot be expanded).  The
             * stack length requirements are described in listsort.txt.  The C
             * version always uses the same stack length (85), but this was
             * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
             * 100 elements) in Java.  Therefore, we use smaller (but sufficiently
             * large) stack lengths for smaller arrays.  The "magic numbers" in the
             * computation below must be changed if MIN_MERGE is decreased.  See
             * the MIN_MERGE declaration above for more information.
             */
            int stackLen = (len <    120  ?  5 :
                            len <   1542  ? 10 :
                            len < 119151  ? 19 : 40);
            runBase = new int[stackLen];
            runLen = new int[stackLen];
        
        }
        /*
         * The next two methods (which are package private and static) constitute
         * the entire API of this class.  Each of these methods obeys the contract
         * of the public method with the same signature in Arrays.Copy.
         */
        /// <summary>
        /// This method constitute the entire API of this class
        /// </summary>
        /// <param name="a">the array to be sorted</param>
        /// <param name="c">the comparator to determine the order of the sort</param>
        public static void sort(T[] a, IComparer<T> c)
        {
            sort(a, 0, a.Length, c);
        }
        /// <summary>
        /// This method constitute the entire API of this class
        /// </summary>
        /// <param name="a">the array to be sorted</param>
        /// <param name="lo"></param>
        /// <param name="hi"></param>
        /// <param name="c">Comparer</param>
        public static void sort(T[] a, int lo, int hi, IComparer<T> c)
        {
            if (c == null) {
                //Arrays.sort(a, lo, hi);
                var work = a.ToList<T>();
                work.Sort();
                a = work.ToArray<T>();
                return;
            }

            rangeCheck(a.Length, lo, hi);
            int nRemaining  = hi - lo;
            if (nRemaining < 2)
                return;  // Arrays of size 0 and 1 are always sorted

            // If array is small, do a "mini-TimSort" with no merges
            if (nRemaining < MIN_MERGE) {
                int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
                binarySort(a, lo, hi, lo + initRunLen, c);
                return;
            }

            /**
             * March over the array once, left to right, finding natural runs,
             * extending short natural runs to minRun elements, and merging runs
             * to maintain stack invariant.
             */
            var ts = new TimSort<T>(a, c);
            int minRun = minRunLength(nRemaining);
            do {
                // Identify next run
                int runLen = countRunAndMakeAscending(a, lo, hi, c);

                // If run is short, extend to min(minRun, nRemaining)
                if (runLen < minRun) {
                    int force = nRemaining <= minRun ? nRemaining : minRun;
                    binarySort(a, lo, lo + force, lo + runLen, c);
                    runLen = force;
                }

                // Push run onto pending-run stack, and maybe merge
                ts.pushRun(lo, runLen);
                ts.mergeCollapse();

                // Advance to find next run
                lo += runLen;
                nRemaining -= runLen;
            } while (nRemaining != 0);

            // Merge all remaining runs to complete sort
            Debug.Assert(lo == hi);
            ts.mergeForceCollapse();
            Debug.Assert(ts.stackSize == 1);
        }
        /// <summary>
        /// Sorts the specified portion of the specified array using a binary
        /// insertion sort.  This is the best method for sorting small numbers
        /// of elements.  It requires O(n log n) compares, but O(n^2) data
        /// movement (worst case).
        /// 
        /// If the initial part of the specified range is already sorted,
        /// this method can take advantage of it: the method assumes that the
        /// elements from index <paramref name="lo"/>, inclusive, to 
        /// <paramref name="start"/>, exclusive are already sorted.
        /// </summary>
        /// <param name="a">the array in which a range is to be sorted</param>
        /// <param name="lo">the index of the first element in the range to be sorted</param>
        /// <param name="hi">the index after the last element in the range to be sorted</param>
        /// <param name="start">the index of the first element in the range 
        /// that is not already known to be sorted (<code> lo <= start <= hi</code></param>
        /// <param name="c">comparator to used for the sort</param>
        private static void binarySort(T[] a, int lo, int hi, int start,
                                           IComparer<T> c)
        {
            Debug.Assert(lo <= start && start <= hi);
            if (start == lo)
                start++;
            for ( ; start < hi; start++) {
                var pivot = a[start];

                // Set left (and right) to the index where a[start] (pivot) belongs
                int left = lo;
                int right = start;
                Debug.Assert(left <= right);
                /*
                 * Invariants:
                 *   pivot >= all in [lo, left).
                 *   pivot <  all in [right, start).
                 */
                while (left < right) {
                    //int mid = (left + right) >>> 1;
                    int mid = (left + right) >> 1;
                    if (c.Compare(pivot, a[mid]) < 0)
                        right = mid;
                    else
                        left = mid + 1;
                }
                Debug.Assert(left == right);

                /*
                 * The invariants still hold: pivot >= all in [lo, left) and
                 * pivot < all in [left, start), so pivot belongs at left.  Note
                 * that if there are elements equal to pivot, left points to the
                 * first slot after them -- that's why this sort is stable.
                 * Slide elements over to make room to make room for pivot.
                 */
                int n = start - left;  // The number of elements to move
                // Switch is just an optimization for arraycopy in default case
                switch(n) {
                    case 2:
                        a[left + 2] = a[left + 1];
                        goto case 1;
                    case 1:
                        a[left + 1] = a[left];
                        break;
                    default:
                        Array.Copy(a, left, a, left + 1, n);
                        break;
                }
                a[left] = pivot;
            }
        }

        /// <summary>
        /// Returns the length of the run beginning at the specified position in
        /// the specified array and reverses the run if it is descending (ensuring
        /// that the run will always be ascending when the method returns).
        /// 
        /// A run is the longest ascending sequence with:
        /// 
        ///    a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
        /// 
        /// or the longest descending sequence with:
        /// 
        ///    a[lo] >  a[lo + 1] >  a[lo + 2] >  ...
        /// 
        /// For its intended use in a stable mergesort, the strictness of the
        /// definition of "descending" is needed so that the call can safely
        /// reverse a descending sequence without violating stability.
        /// </summary>
        /// <param name="a">the array in which a run is to be counted and possibly reversed</param>
        /// <param name="lo">index of the first element in the run</param>
        /// <param name="hi">index after the last element that may be contained in the run. It is required that <code>lo < hi</code>.</param>
        /// <param name="c">the comparator to used for the sort</param>
        /// <returns>the length of the run beginning at the specified position in the specified array</returns>
        private static int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                        IComparer<T> c)
        {
            Debug.Assert(lo < hi);
            int runHi = lo + 1;
            if (runHi == hi)
                return 1;

            // Find end of run, and reverse range if descending
            if (c.Compare(a[runHi++], a[lo]) < 0) { // Descending
                while(runHi < hi && c.Compare(a[runHi], a[runHi - 1]) < 0)
                    runHi++;
                reverseRange(a, lo, runHi);
            } else {                              // Ascending
                while (runHi < hi && c.Compare(a[runHi], a[runHi - 1]) >= 0)
                    runHi++;
            }

            return runHi - lo;
        }
        /// <summary>
        /// Reverse the specified range of the specified array.
        /// </summary>
        /// <param name="a">the array in which a range is to be reversed</param>
        /// <param name="lo">the index of the first element in the range to be reversed</param>
        /// <param name="hi">the index after the last element in the range to be reversed</param>
        private static void reverseRange(T[] a, int lo, int hi)
        {
            hi--;
            while (lo < hi)
            {
                var t = a[lo];
                a[lo++] = a[hi];
                a[hi--] = t;
            }
        }
        /// <summary>
        /// Returns the minimum acceptable run length for an array of the specified
        /// length. Natural runs shorter than this will be extended with
        /// <see >#binarySort</see>.
        /// Roughly speaking, the computation is:
        /// 
        ///  If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
        ///  Else if n is an exact power of 2, return MIN_MERGE/2.
        ///  Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
        ///   is close to, but strictly less than, an exact power of 2.
        /// 
        /// For the rationale, see listsort.txt.
        /// </summary>
        /// <param name="n">the length of the array to be sorted</param>
        /// <returns>the length of the minimum run to be merged</returns>
        private static int minRunLength(int n) {
            Debug.Assert(n >= 0);
            int r = 0;      // Becomes 1 if any 1 bits are shifted off
            while (n >= MIN_MERGE) {
                r |= (n & 1);
                n >>= 1;
            }
            return n + r;
        }
        /// <summary>
        /// Pushes the specified run onto the pending-run stack.
        /// </summary>
        /// <param name="runBase">index of the first element in the run</param>
        /// <param name="runLen">the number of elements in the run</param>
        private void pushRun(int runBase, int runLen)
        {
            this.runBase[stackSize] = runBase;
            this.runLen[stackSize] = runLen;
            stackSize++;
        }

        /// <summary>
        /// Examines the stack of runs waiting to be merged and merges adjacent runs
        /// until the stack invariants are reestablished:
        /// 
        ///     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
        ///     2. runLen[i - 2] > runLen[i - 1]
        /// 
        /// This method is called each time a new run is pushed onto the stack,
        /// so the invariants are guaranteed to hold for i < stackSize upon
        /// entry to the method.
        /// </summary>
        private void mergeCollapse()
        {
            while (stackSize > 1)
            {
                int n = stackSize - 2;
                if (n > 0 && runLen[n - 1] <= runLen[n] + runLen[n + 1])
                {
                    if (runLen[n - 1] < runLen[n + 1])
                        n--;
                    mergeAt(n);
                }
                else if (runLen[n] <= runLen[n + 1])
                {
                    mergeAt(n);
                }
                else
                {
                    break; // Invariant is established
                }
            }
        }
        /// <summary>
        /// Merges all runs on the stack until only one remains.
        /// This method is called once, to complete the sort.
        /// </summary>
        private void mergeForceCollapse()
        {
            while (stackSize > 1)
            {
                int n = stackSize - 2;
                if (n > 0 && runLen[n - 1] < runLen[n + 1])
                    n--;
                mergeAt(n);
            }
        }

        /// <summary>
        /// Merges the two runs at stack indices i and i+1.  Run i must be
        /// the penultimate or antepenultimate run on the stack.  In other words,
        /// i must be equal to stackSize-2 or stackSize-3.
        /// </summary>
        /// <param name="i">stack index of the first of the two runs to merge</param>
        private void mergeAt(int i)
        {
            Debug.Assert(stackSize >= 2);
            Debug.Assert(i >= 0);
            Debug.Assert(i == stackSize - 2 || i == stackSize - 3);

            int base1 = runBase[i];
            int len1 = runLen[i];
            int base2 = runBase[i + 1];
            int len2 = runLen[i + 1];
            Debug.Assert(len1 > 0 && len2 > 0);
            Debug.Assert(base1 + len1 == base2);

            /*
             * Record the length of the combined runs; if i is the 3rd-last
             * run now, also slide over the last run (which isn't involved
             * in this merge).  The current run (i+1) goes away in any case.
             */
            runLen[i] = len1 + len2;
            if (i == stackSize - 3) {
                runBase[i + 1] = runBase[i + 2];
                runLen[i + 1] = runLen[i + 2];
            }
            stackSize--;

            /*
             * Find where the first element of run2 goes in run1. Prior elements
             * in run1 can be ignored (because they're already in place).
             */
            int k = gallopRight(a[base2], a, base1, len1, 0, c);
            Debug.Assert(k >= 0);
            base1 += k;
            len1 -= k;
            if (len1 == 0)
                return;

            /*
             * Find where the last element of run1 goes in run2. Subsequent elements
             * in run2 can be ignored (because they're already in place).
             */
            len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
            Debug.Assert(len2 >= 0);
            if (len2 == 0)
                return;

            // Merge remaining runs, using tmp array with min(len1, len2) elements
            if (len1 <= len2)
                mergeLo(base1, len1, base2, len2);
            else
                mergeHi(base1, len1, base2, len2);
        }

        /// <summary>
        /// Locates the position at which to insert the specified key into the
        /// specified sorted range; if the range contains an element equal to key,
        /// returns the index of the leftmost equal element.
        /// </summary>
        /// <param name="key">the key whose insertion point to search for</param>
        /// <param name="a">the array in which to search</param>
        /// <param name="basei">the index of the first element in the range</param>
        /// <param name="len">the length of the range; must be > 0</param>
        /// <param name="hint">
        /// the index at which to begin the search, 0 <= hint < n.
        /// The closer hint is to the result, the faster this method will run.
        /// </param>
        /// <param name="c">the comparator used to order the range, and to search</param>
        /// <returns>
        /// the int k,  0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
        /// pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
        /// In other words, key belongs at index b + k; or in other words,
        /// the first k elements of a should precede key, and the last n - k
        /// should follow it.
        /// </returns>
        private static int gallopLeft(T key, T[] a, int basei, int len, int hint,
                                          IComparer<T> c)
        {
            Debug.Assert(len > 0 && hint >= 0 && hint < len);
            int lastOfs = 0;
            int ofs = 1;
            if (c.Compare(key, a[basei + hint]) > 0) {
                // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
                int maxOfs = len - hint;
                while (ofs < maxOfs && c.Compare(key, a[basei + hint + ofs]) > 0) {
                    lastOfs = ofs;
                    ofs = (ofs << 1) + 1;
                    if (ofs <= 0)   // int overflow
                        ofs = maxOfs;
                }
                if (ofs > maxOfs)
                    ofs = maxOfs;

                // Make offsets relative to base
                lastOfs += hint;
                ofs += hint;
            } else { // key <= a[base + hint]
                // Gallop left until a[basei+hint-ofs] < key <= a[basei+hint-lastOfs]
                int maxOfs = hint + 1;
                while (ofs < maxOfs && c.Compare(key, a[basei + hint - ofs]) <= 0) {
                    lastOfs = ofs;
                    ofs = (ofs << 1) + 1;
                    if (ofs <= 0)   // int overflow
                        ofs = maxOfs;
                }
                if (ofs > maxOfs)
                    ofs = maxOfs;

                // Make offsets relative to base
                int tmp = lastOfs;
                lastOfs = hint - ofs;
                ofs = hint - tmp;
            }
            Debug.Assert(-1 <= lastOfs && lastOfs < ofs && ofs <= len);

            /*
             * Now a[base+lastOfs] < key <= a[basei+ofs], so key belongs somewhere
             * to the right of lastOfs but no farther right than ofs.  Do a binary
             * search, with invariant a[basei + lastOfs - 1] < key <= a[basei + ofs].
             */
            lastOfs++;
            while (lastOfs < ofs) {
                //int m = lastOfs + ((ofs - lastOfs) >>> 1);
                int m = lastOfs + ((ofs - lastOfs) >> 1);

                if (c.Compare(key, a[basei + m]) > 0)
                    lastOfs = m + 1;  // a[basei + m] < key
                else
                    ofs = m;          // key <= a[basei + m]
            }
            Debug.Assert(lastOfs == ofs);   // so a[basei + ofs - 1] < key <= a[base + ofs]
            return ofs;
        }
        /// <summary>
        /// Like gallopLeft, except that if the range contains an element equal to
        /// key, gallopRight returns the index after the rightmost equal element.
        /// </summary>
        /// <param name="key">the key whose insertion point to search for</param>
        /// <param name="a">the array in which to search</param>
        /// <param name="basei">the index of the first element in the range</param>
        /// <param name="len">the length of the range; must be > 0</param>
        /// <param name="hint">
        /// the index at which to begin the search, 0 <= hint < n.
        /// The closer hint is to the result, the faster this method will run.
        /// </param>
        /// <param name="c">the comparator used to order the range, and to search</param>
        /// <returns>the int k,  0 <= k <= n such that a[b + k - 1] <= key < a[b + k]</returns>
        private static int gallopRight(T key, T[] a, int basei, int len,
                                           int hint, IComparer<T> c)
        {
            Debug.Assert(len > 0 && hint >= 0 && hint < len);

            int ofs = 1;
            int lastOfs = 0;
            if (c.Compare(key, a[basei + hint]) < 0) {
                // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
                int maxOfs = hint + 1;
                while (ofs < maxOfs && c.Compare(key, a[basei + hint - ofs]) < 0) {
                    lastOfs = ofs;
                    ofs = (ofs << 1) + 1;
                    if (ofs <= 0)   // int overflow
                        ofs = maxOfs;
                }
                if (ofs > maxOfs)
                    ofs = maxOfs;

                // Make offsets relative to b
                int tmp = lastOfs;
                lastOfs = hint - ofs;
                ofs = hint - tmp;
            } else { // a[b + hint] <= key
                // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
                int maxOfs = len - hint;
                while (ofs < maxOfs && c.Compare(key, a[basei + hint + ofs]) >= 0) {
                    lastOfs = ofs;
                    ofs = (ofs << 1) + 1;
                    if (ofs <= 0)   // int overflow
                        ofs = maxOfs;
                }
                if (ofs > maxOfs)
                    ofs = maxOfs;

                // Make offsets relative to b
                lastOfs += hint;
                ofs += hint;
            }
            Debug.Assert(-1 <= lastOfs && lastOfs < ofs && ofs <= len);

            /*
             * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
             * the right of lastOfs but no farther right than ofs.  Do a binary
             * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
             */
            lastOfs++;
            while (lastOfs < ofs) {
                //int m = lastOfs + ((ofs - lastOfs) >>> 1);
                int m = lastOfs + ((ofs - lastOfs) >> 1);

                if (c.Compare(key, a[basei + m]) < 0)
                    ofs = m;          // key < a[b + m]
                else
                    lastOfs = m + 1;  // a[b + m] <= key
            }
            Debug.Assert(lastOfs == ofs);  // so a[b + ofs - 1] <= key < a[b + ofs]
            return ofs;
        }
        /// <summary>
        /// Merges two adjacent runs in place, in a stable fashion.  The first
        /// element of the first run must be greater than the first element of the
        /// second run (a[base1] > a[base2]), and the last element of the first run
        /// (a[base1 + len1-1]) must be greater than all elements of the second run.
        /// 
        /// For performance, this method should be called only when len1 <= len2;
        /// its twin, mergeHi should be called if len1 >= len2.  (Either method
        /// may be called if len1 == len2.)
        /// </summary>
        /// <param name="base1">index of first element in first run to be merged</param>
        /// <param name="len1">length of first run to be merged (must be > 0)</param>
        /// <param name="base2">index of first element in second run to be merged (must be aBase + aLen)</param>
        /// <param name="len2">length of second run to be merged (must be > 0)</param>
        private void mergeLo(int base1, int len1, int base2, int len2) {
            Debug.Assert(len1 > 0 && len2 > 0 && base1 + len1 == base2);

            // Copy first run into temp array
            var a = this.a; // For performance
            var tmp = ensureCapacity(len1);
            Array.Copy(a, base1, tmp, 0, len1);

            int cursor1 = 0;       // Indexes into tmp array
            int cursor2 = base2;   // Indexes int a
            int dest = base1;      // Indexes int a

            // Move first element of second run and deal with degenerate cases
            a[dest++] = a[cursor2++];
            if (--len2 == 0) {
                Array.Copy(tmp, cursor1, a, dest, len1);
                return;
            }
            if (len1 == 1) {
                Array.Copy(a, cursor2, a, dest, len2);
                a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
                return;
            }

            var c = this.c;  // Use local variable for performance
            int minGallop = this.minGallop;    //  "    "       "     "      "
        outer:
            while (true) {
                int count1 = 0; // Number of times in a row that first run won
                int count2 = 0; // Number of times in a row that second run won

                /*
                 * Do the straightforward thing until (if ever) one run starts
                 * winning consistently.
                 */
                do {
                    Debug.Assert(len1 > 1 && len2 > 0);
                    if (c.Compare(a[cursor2], tmp[cursor1]) < 0) {
                        a[dest++] = a[cursor2++];
                        count2++;
                        count1 = 0;
                        if (--len2 == 0)
                            goto outer;
                    } else {
                        a[dest++] = tmp[cursor1++];
                        count1++;
                        count2 = 0;
                        if (--len1 == 1)
                            goto outer;
                    }
                } while ((count1 | count2) < minGallop);

                /*
                 * One run is winning so consistently that galloping may be a
                 * huge win. So try that, and continue galloping until (if ever)
                 * neither run appears to be winning consistently anymore.
                 */
                do {
                    Debug.Assert(len1 > 1 && len2 > 0);
                    count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
                    if (count1 != 0) {
                        Array.Copy(tmp, cursor1, a, dest, count1);
                        dest += count1;
                        cursor1 += count1;
                        len1 -= count1;
                        if (len1 <= 1) // len1 == 1 || len1 == 0
                            goto outer;
                    }
                    a[dest++] = a[cursor2++];
                    if (--len2 == 0)
                        goto outer;

                    count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
                    if (count2 != 0) {
                        Array.Copy(a, cursor2, a, dest, count2);
                        dest += count2;
                        cursor2 += count2;
                        len2 -= count2;
                        if (len2 == 0)
                            goto outer;
                    }
                    a[dest++] = tmp[cursor1++];
                    if (--len1 == 1)
                        goto outer;
                    minGallop--;
                } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
                if (minGallop < 0)
                    minGallop = 0;
                minGallop += 2;  // Penalize for leaving gallop mode
            }  // End of "outer" loop
            this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field

            if (len1 == 1) {
                Debug.Assert(len2 > 0);
                Array.Copy(a, cursor2, a, dest, len2);
                a[dest + len2] = tmp[cursor1]; //  Last elt of run 1 to end of merge
            } else if (len1 == 0) {
                throw new ArgumentException(
                    "Comparison method violates its general contract!");
            } else {
                Debug.Assert(len2 == 0);
                Debug.Assert(len1 > 1);
                Array.Copy(tmp, cursor1, a, dest, len1);
            }
        }
        /// <summary>
        /// Like mergeLo, except that this method should be called only if
        /// len1 >= len2; mergeLo should be called if len1 <= len2.  (Either method
        /// may be called if len1 == len2.)
        /// </summary>
        /// <param name="base1">index of first element in first run to be merged</param>
        /// <param name="len1">length of first run to be merged (must be > 0)</param>
        /// <param name="base2">index of first element in second run to be merged (must be aBase + aLen)</param>
        /// <param name="len2">length of second run to be merged (must be > 0)</param>
        private void mergeHi(int base1, int len1, int base2, int len2) {
            Debug.Assert(len1 > 0 && len2 > 0 && base1 + len1 == base2);

            // Copy second run into temp array
            T[] a = this.a; // For performance
            T[] tmp = ensureCapacity(len2);
            Array.Copy(a, base2, tmp, 0, len2);

            int cursor1 = base1 + len1 - 1;  // Indexes into a
            int cursor2 = len2 - 1;          // Indexes into tmp array
            int dest = base2 + len2 - 1;     // Indexes into a

            // Move last element of first run and deal with degenerate cases
            a[dest--] = a[cursor1--];
            if (--len1 == 0) {
                Array.Copy(tmp, 0, a, dest - (len2 - 1), len2);
                return;
            }
            if (len2 == 1) {
                dest -= len1;
                cursor1 -= len1;
                Array.Copy(a, cursor1 + 1, a, dest + 1, len1);
                a[dest] = tmp[cursor2];
                return;
            }

            var c = this.c;  // Use local variable for performance
            int minGallop = this.minGallop;    //  "    "       "     "      "
        outer:
            while (true) {
                int count1 = 0; // Number of times in a row that first run won
                int count2 = 0; // Number of times in a row that second run won

                /*
                 * Do the straightforward thing until (if ever) one run
                 * appears to win consistently.
                 */
                do {
                    Debug.Assert(len1 > 0 && len2 > 1);
                    if (c.Compare(tmp[cursor2], a[cursor1]) < 0) {
                        a[dest--] = a[cursor1--];
                        count1++;
                        count2 = 0;
                        if (--len1 == 0)
                            goto outer;
                    } else {
                        a[dest--] = tmp[cursor2--];
                        count2++;
                        count1 = 0;
                        if (--len2 == 1)
                            goto outer;
                    }
                } while ((count1 | count2) < minGallop);

                /*
                 * One run is winning so consistently that galloping may be a
                 * huge win. So try that, and continue galloping until (if ever)
                 * neither run appears to be winning consistently anymore.
                 */
                do {
                    Debug.Assert(len1 > 0 && len2 > 1);
                    count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
                    if (count1 != 0) {
                        dest -= count1;
                        cursor1 -= count1;
                        len1 -= count1;
                        Array.Copy(a, cursor1 + 1, a, dest + 1, count1);
                        if (len1 == 0)
                            goto outer;
                    }
                    a[dest--] = tmp[cursor2--];
                    if (--len2 == 1)
                        goto outer;

                    count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c);
                    if (count2 != 0) {
                        dest -= count2;
                        cursor2 -= count2;
                        len2 -= count2;
                        Array.Copy(tmp, cursor2 + 1, a, dest + 1, count2);
                        if (len2 <= 1)  // len2 == 1 || len2 == 0
                            goto outer;
                    }
                    a[dest--] = a[cursor1--];
                    if (--len1 == 0)
                        goto outer;
                    minGallop--;
                } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
                if (minGallop < 0)
                    minGallop = 0;
                minGallop += 2;  // Penalize for leaving gallop mode
            }  // End of "outer" loop
            this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field

            if (len2 == 1) {
                Debug.Assert(len1 > 0);
                dest -= len1;
                cursor1 -= len1;
                Array.Copy(a, cursor1 + 1, a, dest + 1, len1);
                a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge
            } else if (len2 == 0) {
                throw new ArgumentException(
                    "Comparison method violates its general contract!");
            } else {
                Debug.Assert(len1 == 0);
                Debug.Assert(len2 > 0);
                Array.Copy(tmp, 0, a, dest - (len2 - 1), len2);
            }
        }

        /// <summary>
        /// Ensures that the external array tmp has at least the specified
        /// number of elements, increasing its size if necessary.  The size
        /// increases exponentially to ensure amortized linear time complexity.
        /// </summary>
        /// <param name="minCapacity">the minimum required capacity of the tmp array</param>
        /// <returns>tmp, whether or not it grew</returns>
        private T[] ensureCapacity(int minCapacity)
        {
            if (tmp.Length < minCapacity)
            {
                // Compute smallest power of 2 > minCapacity
                int newSize = minCapacity;
                newSize |= newSize >> 1;
                newSize |= newSize >> 2;
                newSize |= newSize >> 4;
                newSize |= newSize >> 8;
                newSize |= newSize >> 16;
                newSize++;

                if (newSize < 0) // Not bloody likely!
                    newSize = minCapacity;
                else
                    //newSize = Math.Min(newSize, a.Length >>> 1);
                    newSize = Math.Min(newSize, a.Length >> 1);

                tmp = new T[newSize];
            }
            return tmp;
        }

        /// <summary>
        /// Checks that fromIndex and toIndex are in range, and throws an
        /// appropriate exception if they aren't.
        /// </summary>
        /// <param name="arrayLen">the length of the array</param>
        /// <param name="fromIndex">the index of the first element of the range</param>
        /// <param name="toIndex">the index after the last element of the range</param>
        /// <exception cref="ArgumentException">if fromIndex > toIndex</exception>
        /// <exception cref="ArgumentOutOfRangeException">if fromIndex < 0 or toIndex > arrayLen</exception>
        private static void rangeCheck(int arrayLen, int fromIndex, int toIndex)
        {
            if (fromIndex > toIndex)
                throw new ArgumentException("fromIndex(" + fromIndex +
                           ") > toIndex(" + toIndex + ")");
            if (fromIndex < 0)
                throw new ArgumentOutOfRangeException("fromIndex", fromIndex.ToString());
            if (toIndex > arrayLen)
                throw new ArgumentOutOfRangeException("toIndex", toIndex.ToString());
        }


    }
}

TimSort.csproj

<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <PropertyGroup>
    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    <ProductVersion>8.0.30703</ProductVersion>
    <SchemaVersion>2.0</SchemaVersion>
    <ProjectGuid>{827ABFA0-7F45-4E57-9B43-DED662CBDAAC}</ProjectGuid>
    <OutputType>Library</OutputType>
    <AppDesignerFolder>Properties</AppDesignerFolder>
    <RootNamespace>TrimSort</RootNamespace>
    <AssemblyName>TimSort</AssemblyName>
    <TargetFrameworkVersion>v4.0</TargetFrameworkVersion>
    <FileAlignment>512</FileAlignment>
  </PropertyGroup>
  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugSymbols>true</DebugSymbols>
    <DebugType>full</DebugType>
    <Optimize>false</Optimize>
    <OutputPath>bin\Debug\</OutputPath>
    <DefineConstants>DEBUG;TRACE</DefineConstants>
    <ErrorReport>prompt</ErrorReport>
    <WarningLevel>4</WarningLevel>
  </PropertyGroup>
  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
    <DebugType>pdbonly</DebugType>
    <Optimize>true</Optimize>
    <OutputPath>bin\Release\</OutputPath>
    <DefineConstants>TRACE</DefineConstants>
    <ErrorReport>prompt</ErrorReport>
    <WarningLevel>4</WarningLevel>
  </PropertyGroup>
  <ItemGroup>
    <Reference Include="nunit.framework, Version=2.5.9.10344, Culture=neutral, PublicKeyToken=96d09a1eb7f44a77, processorArchitecture=MSIL" />
    <Reference Include="System" />
    <Reference Include="System.Core" />
    <Reference Include="System.Xml.Linq" />
    <Reference Include="System.Data.DataSetExtensions" />
    <Reference Include="Microsoft.CSharp" />
    <Reference Include="System.Data" />
    <Reference Include="System.Xml" />
  </ItemGroup>
  <ItemGroup>
    <Compile Include="Comparers.cs" />
    <Compile Include="TimSort.cs" />
    <Compile Include="Properties\AssemblyInfo.cs" />
    <Compile Include="TimSortTest.cs" />
  </ItemGroup>
  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
       Other similar extension points exist, see Microsoft.Common.targets.
  <Target Name="BeforeBuild">
  </Target>
  <Target Name="AfterBuild">
  </Target>
  -->
</Project>

TimSort.sln


Microsoft Visual Studio Solution File, Format Version 11.00
# Visual C# Express 2010
Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "TimSort", ".\TimSort.csproj", "{827ABFA0-7F45-4E57-9B43-DED662CBDAAC}"
EndProject
Global
	GlobalSection(SolutionConfigurationPlatforms) = preSolution
		Debug|Any CPU = Debug|Any CPU
		Release|Any CPU = Release|Any CPU
	EndGlobalSection
	GlobalSection(ProjectConfigurationPlatforms) = postSolution
		{827ABFA0-7F45-4E57-9B43-DED662CBDAAC}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
		{827ABFA0-7F45-4E57-9B43-DED662CBDAAC}.Debug|Any CPU.Build.0 = Debug|Any CPU
		{827ABFA0-7F45-4E57-9B43-DED662CBDAAC}.Release|Any CPU.ActiveCfg = Release|Any CPU
		{827ABFA0-7F45-4E57-9B43-DED662CBDAAC}.Release|Any CPU.Build.0 = Release|Any CPU
	EndGlobalSection
	GlobalSection(SolutionProperties) = preSolution
		HideSolutionNode = FALSE
	EndGlobalSection
EndGlobal

TimSortTest.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;

namespace TrimSort
{
    [TestFixture()]
    class TimSortTest
    {
        [SetUp()]
        public void SetUp()
        {
        
        }
        [TearDown()]
        public void TearDown()
        {
        }

        [Test()]
        public void SortTest()
        {
            int[] seed = { 5,7,8,10,324,888,9};
            var checks = new List<int>(seed);

            checks.Sort();
            TimSort.TimSort<int>.sort(seed, new Comparers.ComparerInt());
            Assert.AreEqual(checks.ToArray(), seed);
        }
    }

    
}