public void sort(Buffer a, int lo, int hi, Comparator<? super K> c) {
        assert c != null;

        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.
         */
        SortState sortState = new SortState(a, c, hi - lo);
        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
            sortState.pushRun(lo, runLen);
            sortState.mergeCollapse();

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

        // Merge all remaining runs to complete sort
        assert lo == hi;
        sortState.mergeForceCollapse();
        assert sortState.stackSize == 1;
    }
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
indexr-query-opt/src/main/java/org/apache/spark/util/collection/TimSort.java