jaroslav@559: /*
jaroslav@559: * Copyright 2009 Google Inc. All Rights Reserved.
jaroslav@559: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jaroslav@559: *
jaroslav@559: * This code is free software; you can redistribute it and/or modify it
jaroslav@559: * under the terms of the GNU General Public License version 2 only, as
jaroslav@559: * published by the Free Software Foundation. Oracle designates this
jaroslav@559: * particular file as subject to the "Classpath" exception as provided
jaroslav@559: * by Oracle in the LICENSE file that accompanied this code.
jaroslav@559: *
jaroslav@559: * This code is distributed in the hope that it will be useful, but WITHOUT
jaroslav@559: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jaroslav@559: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
jaroslav@559: * version 2 for more details (a copy is included in the LICENSE file that
jaroslav@559: * accompanied this code).
jaroslav@559: *
jaroslav@559: * You should have received a copy of the GNU General Public License version
jaroslav@559: * 2 along with this work; if not, write to the Free Software Foundation,
jaroslav@559: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jaroslav@559: *
jaroslav@559: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
jaroslav@559: * or visit www.oracle.com if you need additional information or have any
jaroslav@559: * questions.
jaroslav@559: */
jaroslav@559:
jaroslav@559: package java.util;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * This is a near duplicate of {@link TimSort}, modified for use with
jaroslav@559: * arrays of objects that implement {@link Comparable}, instead of using
jaroslav@559: * explicit comparators.
jaroslav@559: *
jaroslav@559: *
If you are using an optimizing VM, you may find that ComparableTimSort
jaroslav@559: * offers no performance benefit over TimSort in conjunction with a
jaroslav@559: * comparator that simply returns {@code ((Comparable)first).compareTo(Second)}.
jaroslav@559: * If this is the case, you are better off deleting ComparableTimSort to
jaroslav@559: * eliminate the code duplication. (See Arrays.java for details.)
jaroslav@559: *
jaroslav@559: * @author Josh Bloch
jaroslav@559: */
jaroslav@559: class ComparableTimSort {
jaroslav@559: /**
jaroslav@559: * This is the minimum sized sequence that will be merged. Shorter
jaroslav@559: * sequences will be lengthened by calling binarySort. If the entire
jaroslav@559: * array is less than this length, no merges will be performed.
jaroslav@559: *
jaroslav@559: * This constant should be a power of two. It was 64 in Tim Peter's C
jaroslav@559: * implementation, but 32 was empirically determined to work better in
jaroslav@559: * this implementation. In the unlikely event that you set this constant
jaroslav@559: * to be a number that's not a power of two, you'll need to change the
jaroslav@559: * {@link #minRunLength} computation.
jaroslav@559: *
jaroslav@559: * If you decrease this constant, you must change the stackLen
jaroslav@559: * computation in the TimSort constructor, or you risk an
jaroslav@559: * ArrayOutOfBounds exception. See listsort.txt for a discussion
jaroslav@559: * of the minimum stack length required as a function of the length
jaroslav@559: * of the array being sorted and the minimum merge sequence length.
jaroslav@559: */
jaroslav@559: private static final int MIN_MERGE = 32;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * The array being sorted.
jaroslav@559: */
jaroslav@559: private final Object[] a;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * When we get into galloping mode, we stay there until both runs win less
jaroslav@559: * often than MIN_GALLOP consecutive times.
jaroslav@559: */
jaroslav@559: private static final int MIN_GALLOP = 7;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * This controls when we get *into* galloping mode. It is initialized
jaroslav@559: * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for
jaroslav@559: * random data, and lower for highly structured data.
jaroslav@559: */
jaroslav@559: private int minGallop = MIN_GALLOP;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * Maximum initial size of tmp array, which is used for merging. The array
jaroslav@559: * can grow to accommodate demand.
jaroslav@559: *
jaroslav@559: * Unlike Tim's original C version, we do not allocate this much storage
jaroslav@559: * when sorting smaller arrays. This change was required for performance.
jaroslav@559: */
jaroslav@559: private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * Temp storage for merges.
jaroslav@559: */
jaroslav@559: private Object[] tmp;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * A stack of pending runs yet to be merged. Run i starts at
jaroslav@559: * address base[i] and extends for len[i] elements. It's always
jaroslav@559: * true (so long as the indices are in bounds) that:
jaroslav@559: *
jaroslav@559: * runBase[i] + runLen[i] == runBase[i + 1]
jaroslav@559: *
jaroslav@559: * so we could cut the storage for this, but it's a minor amount,
jaroslav@559: * and keeping all the info explicit simplifies the code.
jaroslav@559: */
jaroslav@559: private int stackSize = 0; // Number of pending runs on stack
jaroslav@559: private final int[] runBase;
jaroslav@559: private final int[] runLen;
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * Creates a TimSort instance to maintain the state of an ongoing sort.
jaroslav@559: *
jaroslav@559: * @param a the array to be sorted
jaroslav@559: */
jaroslav@559: private ComparableTimSort(Object[] a) {
jaroslav@559: this.a = a;
jaroslav@559:
jaroslav@559: // Allocate temp storage (which may be increased later if necessary)
jaroslav@559: int len = a.length;
jaroslav@559: @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
jaroslav@559: Object[] newArray = new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
jaroslav@559: len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
jaroslav@559: tmp = newArray;
jaroslav@559:
jaroslav@559: /*
jaroslav@559: * Allocate runs-to-be-merged stack (which cannot be expanded). The
jaroslav@559: * stack length requirements are described in listsort.txt. The C
jaroslav@559: * version always uses the same stack length (85), but this was
jaroslav@559: * measured to be too expensive when sorting "mid-sized" arrays (e.g.,
jaroslav@559: * 100 elements) in Java. Therefore, we use smaller (but sufficiently
jaroslav@559: * large) stack lengths for smaller arrays. The "magic numbers" in the
jaroslav@559: * computation below must be changed if MIN_MERGE is decreased. See
jaroslav@559: * the MIN_MERGE declaration above for more information.
jaroslav@559: */
jaroslav@559: int stackLen = (len < 120 ? 5 :
jaroslav@559: len < 1542 ? 10 :
jaroslav@559: len < 119151 ? 19 : 40);
jaroslav@559: runBase = new int[stackLen];
jaroslav@559: runLen = new int[stackLen];
jaroslav@559: }
jaroslav@559:
jaroslav@559: /*
jaroslav@559: * The next two methods (which are package private and static) constitute
jaroslav@559: * the entire API of this class. Each of these methods obeys the contract
jaroslav@559: * of the public method with the same signature in java.util.Arrays.
jaroslav@559: */
jaroslav@559:
jaroslav@559: static void sort(Object[] a) {
jaroslav@559: sort(a, 0, a.length);
jaroslav@559: }
jaroslav@559:
jaroslav@559: static void sort(Object[] a, int lo, int hi) {
jaroslav@559: rangeCheck(a.length, lo, hi);
jaroslav@559: int nRemaining = hi - lo;
jaroslav@559: if (nRemaining < 2)
jaroslav@559: return; // Arrays of size 0 and 1 are always sorted
jaroslav@559:
jaroslav@559: // If array is small, do a "mini-TimSort" with no merges
jaroslav@559: if (nRemaining < MIN_MERGE) {
jaroslav@559: int initRunLen = countRunAndMakeAscending(a, lo, hi);
jaroslav@559: binarySort(a, lo, hi, lo + initRunLen);
jaroslav@559: return;
jaroslav@559: }
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * March over the array once, left to right, finding natural runs,
jaroslav@559: * extending short natural runs to minRun elements, and merging runs
jaroslav@559: * to maintain stack invariant.
jaroslav@559: */
jaroslav@559: ComparableTimSort ts = new ComparableTimSort(a);
jaroslav@559: int minRun = minRunLength(nRemaining);
jaroslav@559: do {
jaroslav@559: // Identify next run
jaroslav@559: int runLen = countRunAndMakeAscending(a, lo, hi);
jaroslav@559:
jaroslav@559: // If run is short, extend to min(minRun, nRemaining)
jaroslav@559: if (runLen < minRun) {
jaroslav@559: int force = nRemaining <= minRun ? nRemaining : minRun;
jaroslav@559: binarySort(a, lo, lo + force, lo + runLen);
jaroslav@559: runLen = force;
jaroslav@559: }
jaroslav@559:
jaroslav@559: // Push run onto pending-run stack, and maybe merge
jaroslav@559: ts.pushRun(lo, runLen);
jaroslav@559: ts.mergeCollapse();
jaroslav@559:
jaroslav@559: // Advance to find next run
jaroslav@559: lo += runLen;
jaroslav@559: nRemaining -= runLen;
jaroslav@559: } while (nRemaining != 0);
jaroslav@559:
jaroslav@559: // Merge all remaining runs to complete sort
jaroslav@559: assert lo == hi;
jaroslav@559: ts.mergeForceCollapse();
jaroslav@559: assert ts.stackSize == 1;
jaroslav@559: }
jaroslav@559:
jaroslav@559: /**
jaroslav@559: * Sorts the specified portion of the specified array using a binary
jaroslav@559: * insertion sort. This is the best method for sorting small numbers
jaroslav@559: * of elements. It requires O(n log n) compares, but O(n^2) data
jaroslav@559: * movement (worst case).
jaroslav@559: *
jaroslav@559: * If the initial part of the specified range is already sorted,
jaroslav@559: * this method can take advantage of it: the method assumes that the
jaroslav@559: * elements from index {@code lo}, inclusive, to {@code start},
jaroslav@559: * exclusive are already sorted.
jaroslav@559: *
jaroslav@559: * @param a the array in which a range is to be sorted
jaroslav@559: * @param lo the index of the first element in the range to be sorted
jaroslav@559: * @param hi the index after the last element in the range to be sorted
jaroslav@559: * @param start the index of the first element in the range that is
jaroslav@559: * not already known to be sorted ({@code lo <= start <= hi})
jaroslav@559: */
jaroslav@559: @SuppressWarnings("fallthrough")
jaroslav@559: private static void binarySort(Object[] a, int lo, int hi, int start) {
jaroslav@559: assert lo <= start && start <= hi;
jaroslav@559: if (start == lo)
jaroslav@559: start++;
jaroslav@559: for ( ; start < hi; start++) {
jaroslav@559: @SuppressWarnings("unchecked")
jaroslav@559: Comparable