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;

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 static 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 static 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 static 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>
        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>
        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
            //assert lo == hi;
            ts.mergeForceCollapse();
            //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)
        {
            //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;
                //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;
                }
                //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) {
            //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
        /// {@link #binarySort}.
        /// 
        /// 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) {
            //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)
        {
            //assert stackSize >= 2;
            //assert i >= 0;
            //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];
            //assert len1 > 0 && len2 > 0;
            //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);
            //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);
            //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) {
            //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;
            }
            //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]
            }
            //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) {
            //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;
            }
            //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
            }
            //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) {
            //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 {
                    //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 {
                    //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) {
                //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 {
                //assert len2 == 0;
                //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) {
            //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 {
                    //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 {
                    //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) {
                //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 {
                //assert len1 == 0;
                //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);

                //@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
                var newArray = (T[]) new T[newSize];
                tmp = newArray;
            }
            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());
        }


    }
}