151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 26e8e72415d6729c9f1de51d1ce5090438002ae3bNarayan Kamath * Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Copyright 2009 Google Inc. All Rights Reserved. 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage java.util; 2851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A stable, adaptive, iterative mergesort that requires far fewer than 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * n lg(n) comparisons when running on partially sorted arrays, while 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * offering performance comparable to a traditional mergesort when run 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * on random arrays. Like all proper mergesorts, this sort is stable and 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * runs O(n log n) time (worst case). In the worst case, this sort requires 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * temporary storage space for n/2 object references; in the best case, 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * it requires only a small constant amount of space. 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This implementation was adapted from Tim Peters's list sort for 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Python, which is described in detail here: 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * http://svn.python.org/projects/python/trunk/Objects/listsort.txt 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Tim's C code may be found here: 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * http://svn.python.org/projects/python/trunk/Objects/listobject.c 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The underlying techniques are described in this paper (and may have 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * even earlier origins): 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * "Optimistic Sorting and Information Theoretic Complexity" 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Peter McIlroy 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), 5351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * pp 467-474, Austin, Texas, 25-27 January 1993. 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * While the API to this class consists solely of static methods, it is 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (privately) instantiable; a TimSort instance holds the state of an ongoing 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sort, assuming the input array is large enough to warrant the full-blown 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * TimSort. Small arrays are sorted in place, using a binary insertion sort. 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiclass TimSort<T> { 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This is the minimum sized sequence that will be merged. Shorter 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sequences will be lengthened by calling binarySort. If the entire 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * array is less than this length, no merges will be performed. 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This constant should be a power of two. It was 64 in Tim Peter's C 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * implementation, but 32 was empirically determined to work better in 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this implementation. In the unlikely event that you set this constant 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to be a number that's not a power of two, you'll need to change the 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #minRunLength} computation. 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If you decrease this constant, you must change the stackLen 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * computation in the TimSort constructor, or you risk an 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ArrayOutOfBounds exception. See listsort.txt for a discussion 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the minimum stack length required as a function of the length 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the array being sorted and the minimum merge sequence length. 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 8051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int MIN_MERGE = 32; 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The array being sorted. 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final T[] a; 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The comparator for this sort. 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final Comparator<? super T> c; 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When we get into galloping mode, we stay there until both runs win less 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * often than MIN_GALLOP consecutive times. 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int MIN_GALLOP = 7; 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This controls when we get *into* galloping mode. It is initialized 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * random data, and lower for highly structured data. 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int minGallop = MIN_GALLOP; 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Maximum initial size of tmp array, which is used for merging. The array 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * can grow to accommodate demand. 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Unlike Tim's original C version, we do not allocate this much storage 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * when sorting smaller arrays. This change was required for performance. 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int INITIAL_TMP_STORAGE_LENGTH = 256; 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 115c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * Temp storage for merges. A workspace array may optionally be 116c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * provided in constructor, and if so will be used as long as it 117c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * is big enough. 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 119c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath private T[] tmp; 120c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath private int tmpBase; // base of tmp array slice 121c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath private int tmpLen; // length of tmp array slice 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A stack of pending runs yet to be merged. Run i starts at 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * address base[i] and extends for len[i] elements. It's always 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * true (so long as the indices are in bounds) that: 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * runBase[i] + runLen[i] == runBase[i + 1] 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * so we could cut the storage for this, but it's a minor amount, 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and keeping all the info explicit simplifies the code. 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int stackSize = 0; // Number of pending runs on stack 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final int[] runBase; 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final int[] runLen; 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a TimSort instance to maintain the state of an ongoing sort. 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array to be sorted 14151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the comparator to determine the order of the sort 142c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param work a workspace array (slice) 143c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param workBase origin of usable space in work array 144c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param workLen usable size of work array 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 146c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) { 14751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.a = a; 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.c = c; 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Allocate temp storage (which may be increased later if necessary) 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = a.length; 152c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ? 153c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath len >>> 1 : INITIAL_TMP_STORAGE_LENGTH; 154c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath if (work == null || workLen < tlen || workBase + tlen > work.length) { 155c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) 156c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath T[] newArray = (T[])java.lang.reflect.Array.newInstance 157c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath (a.getClass().getComponentType(), tlen); 158c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmp = newArray; 159c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmpBase = 0; 160c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmpLen = tlen; 161c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath } 162c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath else { 163c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmp = work; 164c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmpBase = workBase; 165c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmpLen = workLen; 166c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath } 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Allocate runs-to-be-merged stack (which cannot be expanded). The 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * stack length requirements are described in listsort.txt. The C 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version always uses the same stack length (85), but this was 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * measured to be too expensive when sorting "mid-sized" arrays (e.g., 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 100 elements) in Java. Therefore, we use smaller (but sufficiently 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * large) stack lengths for smaller arrays. The "magic numbers" in the 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * computation below must be changed if MIN_MERGE is decreased. See 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the MIN_MERGE declaration above for more information. 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int stackLen = (len < 120 ? 5 : 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len < 1542 ? 10 : 1806e8e72415d6729c9f1de51d1ce5090438002ae3bNarayan Kamath len < 119151 ? 24 : 40); 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runBase = new int[stackLen]; 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runLen = new int[stackLen]; 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 186c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * The next method (package private and static) constitutes the 187c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * entire API of this class. 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 190c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath /** 191c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * Sorts the given range, using the given workspace array slice 192c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * for temp storage when possible. This method is designed to be 193c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * invoked from public methods (in class Arrays) after performing 194c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * any necessary array bounds checks and expanding parameters into 195c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * the required forms. 196c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * 197c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param a the array to be sorted 198c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param lo the index of the first element, inclusive, to be sorted 199c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param hi the index of the last element, exclusive, to be sorted 200c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param c the comparator to use 201c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param work a workspace array (slice) 202c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param workBase origin of usable space in work array 203c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @param workLen usable size of work array 204c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath * @since 1.8 205c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath */ 206c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, 207c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath T[] work, int workBase, int workLen) { 208c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; 20902f409d949c9d50806809b827ec503765bed34fdPrzemyslaw Szczepaniak 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int nRemaining = hi - lo; 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (nRemaining < 2) 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; // Arrays of size 0 and 1 are always sorted 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If array is small, do a "mini-TimSort" with no merges 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (nRemaining < MIN_MERGE) { 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int initRunLen = countRunAndMakeAscending(a, lo, hi, c); 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski binarySort(a, lo, hi, lo + initRunLen, c); 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * March over the array once, left to right, finding natural runs, 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * extending short natural runs to minRun elements, and merging runs 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to maintain stack invariant. 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 226c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int minRun = minRunLength(nRemaining); 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Identify next run 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int runLen = countRunAndMakeAscending(a, lo, hi, c); 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If run is short, extend to min(minRun, nRemaining) 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (runLen < minRun) { 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int force = nRemaining <= minRun ? nRemaining : minRun; 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski binarySort(a, lo, lo + force, lo + runLen, c); 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runLen = force; 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Push run onto pending-run stack, and maybe merge 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ts.pushRun(lo, runLen); 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ts.mergeCollapse(); 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Advance to find next run 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lo += runLen; 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski nRemaining -= runLen; 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while (nRemaining != 0); 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Merge all remaining runs to complete sort 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert lo == hi; 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ts.mergeForceCollapse(); 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert ts.stackSize == 1; 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Sorts the specified portion of the specified array using a binary 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * insertion sort. This is the best method for sorting small numbers 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of elements. It requires O(n log n) compares, but O(n^2) data 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * movement (worst case). 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the initial part of the specified range is already sorted, 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this method can take advantage of it: the method assumes that the 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * elements from index {@code lo}, inclusive, to {@code start}, 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exclusive are already sorted. 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array in which a range is to be sorted 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param lo the index of the first element in the range to be sorted 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param hi the index after the last element in the range to be sorted 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param start the index of the first element in the range that is 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * not already known to be sorted ({@code lo <= start <= hi}) 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c comparator to used for the sort 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski @SuppressWarnings("fallthrough") 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static <T> void binarySort(T[] a, int lo, int hi, int start, 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparator<? super T> c) { 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert lo <= start && start <= hi; 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (start == lo) 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski start++; 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for ( ; start < hi; start++) { 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T pivot = a[start]; 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Set left (and right) to the index where a[start] (pivot) belongs 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int left = lo; 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int right = start; 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert left <= right; 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Invariants: 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * pivot >= all in [lo, left). 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * pivot < all in [right, start). 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (left < right) { 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int mid = (left + right) >>> 1; 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(pivot, a[mid]) < 0) 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski right = mid; 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski left = mid + 1; 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert left == right; 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The invariants still hold: pivot >= all in [lo, left) and 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * pivot < all in [left, start), so pivot belongs at left. Note 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that if there are elements equal to pivot, left points to the 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * first slot after them -- that's why this sort is stable. 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Slide elements over to make room for pivot. 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int n = start - left; // The number of elements to move 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Switch is just an optimization for arraycopy in default case 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski switch (n) { 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case 2: a[left + 2] = a[left + 1]; 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski case 1: a[left + 1] = a[left]; 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski default: System.arraycopy(a, left, a, left + 1, n); 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[left] = pivot; 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the length of the run beginning at the specified position in 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the specified array and reverses the run if it is descending (ensuring 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that the run will always be ascending when the method returns). 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A run is the longest ascending sequence with: 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or the longest descending sequence with: 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a[lo] > a[lo + 1] > a[lo + 2] > ... 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * For its intended use in a stable mergesort, the strictness of the 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * definition of "descending" is needed so that the call can safely 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * reverse a descending sequence without violating stability. 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array in which a run is to be counted and possibly reversed 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param lo index of the first element in the run 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param hi index after the last element that may be contained in the run. 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski It is required that {@code lo < hi}. 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the comparator to used for the sort 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the length of the run beginning at the specified position in 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the specified array 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparator<? super T> c) { 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert lo < hi; 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int runHi = lo + 1; 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (runHi == hi) 34851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return 1; 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Find end of run, and reverse range if descending 35151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(a[runHi++], a[lo]) < 0) { // Descending 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runHi++; 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski reverseRange(a, lo, runHi); 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { // Ascending 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) 35751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runHi++; 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return runHi - lo; 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Reverse the specified range of the specified array. 36551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 36651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array in which a range is to be reversed 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param lo the index of the first element in the range to be reversed 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param hi the index after the last element in the range to be reversed 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static void reverseRange(Object[] a, int lo, int hi) { 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski hi--; 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (lo < hi) { 37351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object t = a[lo]; 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[lo++] = a[hi]; 37551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[hi--] = t; 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the minimum acceptable run length for an array of the specified 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * length. Natural runs shorter than this will be extended with 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #binarySort}. 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Roughly speaking, the computation is: 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). 38751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Else if n is an exact power of 2, return MIN_MERGE/2. 38851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is close to, but strictly less than, an exact power of 2. 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * For the rationale, see listsort.txt. 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param n the length of the array to be sorted 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the length of the minimum run to be merged 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int minRunLength(int n) { 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert n >= 0; 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int r = 0; // Becomes 1 if any 1 bits are shifted off 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (n >= MIN_MERGE) { 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski r |= (n & 1); 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski n >>= 1; 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return n + r; 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Pushes the specified run onto the pending-run stack. 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param runBase index of the first element in the run 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param runLen the number of elements in the run 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void pushRun(int runBase, int runLen) { 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.runBase[stackSize] = runBase; 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.runLen[stackSize] = runLen; 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski stackSize++; 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 41951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Examines the stack of runs waiting to be merged and merges adjacent runs 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * until the stack invariants are reestablished: 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2. runLen[i - 2] > runLen[i - 1] 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method is called each time a new run is pushed onto the stack, 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * so the invariants are guaranteed to hold for i < stackSize upon 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * entry to the method. 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void mergeCollapse() { 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (stackSize > 1) { 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int n = stackSize - 2; 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (runLen[n - 1] < runLen[n + 1]) 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski n--; 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski mergeAt(n); 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else if (runLen[n] <= runLen[n + 1]) { 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski mergeAt(n); 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; // Invariant is established 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Merges all runs on the stack until only one remains. This method is 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * called once, to complete the sort. 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void mergeForceCollapse() { 44951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (stackSize > 1) { 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int n = stackSize - 2; 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (n > 0 && runLen[n - 1] < runLen[n + 1]) 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski n--; 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski mergeAt(n); 45451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Merges the two runs at stack indices i and i+1. Run i must be 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the penultimate or antepenultimate run on the stack. In other words, 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * i must be equal to stackSize-2 or stackSize-3. 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param i stack index of the first of the two runs to merge 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void mergeAt(int i) { 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert stackSize >= 2; 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert i >= 0; 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert i == stackSize - 2 || i == stackSize - 3; 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int base1 = runBase[i]; 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len1 = runLen[i]; 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int base2 = runBase[i + 1]; 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len2 = runLen[i + 1]; 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 0 && len2 > 0; 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert base1 + len1 == base2; 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Record the length of the combined runs; if i is the 3rd-last 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * run now, also slide over the last run (which isn't involved 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in this merge). The current run (i+1) goes away in any case. 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runLen[i] = len1 + len2; 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (i == stackSize - 3) { 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runBase[i + 1] = runBase[i + 2]; 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski runLen[i + 1] = runLen[i + 2]; 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski stackSize--; 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Find where the first element of run2 goes in run1. Prior elements 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in run1 can be ignored (because they're already in place). 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int k = gallopRight(a[base2], a, base1, len1, 0, c); 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert k >= 0; 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski base1 += k; 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len1 -= k; 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len1 == 0) 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Find where the last element of run1 goes in run2. Subsequent elements 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in run2 can be ignored (because they're already in place). 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c); 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len2 >= 0; 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len2 == 0) 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Merge remaining runs, using tmp array with min(len1, len2) elements 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len1 <= len2) 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski mergeLo(base1, len1, base2, len2); 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski mergeHi(base1, len1, base2, len2); 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Locates the position at which to insert the specified key into the 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified sorted range; if the range contains an element equal to key, 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * returns the index of the leftmost equal element. 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 52051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the key whose insertion point to search for 52151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array in which to search 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param base the index of the first element in the range 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param len the length of the range; must be > 0 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param hint the index at which to begin the search, 0 <= hint < n. 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The closer hint is to the result, the faster this method will run. 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the comparator used to order the range, and to search 52751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k], 52851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * pretending that a[b - 1] is minus infinity and a[b + n] is infinity. 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * In other words, key belongs at index b + k; or in other words, 53051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the first k elements of a should precede key, and the last n - k 53151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * should follow it. 53251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 53351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint, 53451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparator<? super T> c) { 53551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len > 0 && hint >= 0 && hint < len; 53651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int lastOfs = 0; 53751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int ofs = 1; 53851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(key, a[base + hint]) > 0) { 53951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs] 54051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int maxOfs = len - hint; 54151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) { 54251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = ofs; 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = (ofs << 1) + 1; 54451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs <= 0) // int overflow 54551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 54651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 54751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs > maxOfs) 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 54951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 55051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Make offsets relative to base 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs += hint; 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs += hint; 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { // key <= a[base + hint] 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs] 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski final int maxOfs = hint + 1; 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) { 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = ofs; 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = (ofs << 1) + 1; 55951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs <= 0) // int overflow 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs > maxOfs) 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Make offsets relative to base 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int tmp = lastOfs; 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = hint - ofs; 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = hint - tmp; 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to the right of lastOfs but no farther right than ofs. Do a binary 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs]. 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs++; 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (lastOfs < ofs) { 57951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int m = lastOfs + ((ofs - lastOfs) >>> 1); 58051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 58151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(key, a[base + m]) > 0) 58251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = m + 1; // a[base + m] < key 58351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 58451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = m; // key <= a[base + m] 58551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs] 58751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return ofs; 58851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 59051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 59151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Like gallopLeft, except that if the range contains an element equal to 59251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * key, gallopRight returns the index after the rightmost equal element. 59351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 59451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the key whose insertion point to search for 59551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array in which to search 59651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param base the index of the first element in the range 59751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param len the length of the range; must be > 0 59851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param hint the index at which to begin the search, 0 <= hint < n. 59951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The closer hint is to the result, the faster this method will run. 60051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the comparator used to order the range, and to search 60151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k] 60251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 60351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static <T> int gallopRight(T key, T[] a, int base, int len, 60451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int hint, Comparator<? super T> c) { 60551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len > 0 && hint >= 0 && hint < len; 60651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 60751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int ofs = 1; 60851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int lastOfs = 0; 60951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(key, a[base + hint]) < 0) { 61051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs] 61151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int maxOfs = hint + 1; 61251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) { 61351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = ofs; 61451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = (ofs << 1) + 1; 61551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs <= 0) // int overflow 61651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 61751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 61851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs > maxOfs) 61951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 62051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 62151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Make offsets relative to b 62251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int tmp = lastOfs; 62351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = hint - ofs; 62451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = hint - tmp; 62551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { // a[b + hint] <= key 62651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs] 62751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int maxOfs = len - hint; 62851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) { 62951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = ofs; 63051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = (ofs << 1) + 1; 63151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs <= 0) // int overflow 63251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 63351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 63451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (ofs > maxOfs) 63551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = maxOfs; 63651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 63751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Make offsets relative to b 63851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs += hint; 63951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs += hint; 64051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 64151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert -1 <= lastOfs && lastOfs < ofs && ofs <= len; 64251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 64351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 64451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to 64551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the right of lastOfs but no farther right than ofs. Do a binary 64651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs]. 64751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 64851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs++; 64951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (lastOfs < ofs) { 65051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int m = lastOfs + ((ofs - lastOfs) >>> 1); 65151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 65251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(key, a[base + m]) < 0) 65351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ofs = m; // key < a[b + m] 65451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 65551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastOfs = m + 1; // a[b + m] <= key 65651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 65751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs] 65851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return ofs; 65951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 66151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 66251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Merges two adjacent runs in place, in a stable fashion. The first 66351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element of the first run must be greater than the first element of the 66451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * second run (a[base1] > a[base2]), and the last element of the first run 66551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (a[base1 + len1-1]) must be greater than all elements of the second run. 66651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 66751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * For performance, this method should be called only when len1 <= len2; 66851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * its twin, mergeHi should be called if len1 >= len2. (Either method 66951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * may be called if len1 == len2.) 67051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 67151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param base1 index of first element in first run to be merged 67251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param len1 length of first run to be merged (must be > 0) 67351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param base2 index of first element in second run to be merged 67451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (must be aBase + aLen) 67551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param len2 length of second run to be merged (must be > 0) 67651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 67751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void mergeLo(int base1, int len1, int base2, int len2) { 67851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 0 && len2 > 0 && base1 + len1 == base2; 67951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 68051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Copy first run into temp array 68151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T[] a = this.a; // For performance 68251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T[] tmp = ensureCapacity(len1); 683c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath int cursor1 = tmpBase; // Indexes into tmp array 68451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int cursor2 = base2; // Indexes int a 68551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int dest = base1; // Indexes int a 686c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath System.arraycopy(a, base1, tmp, cursor1, len1); 68751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 68851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Move first element of second run and deal with degenerate cases 68951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest++] = a[cursor2++]; 69051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len2 == 0) { 69151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(tmp, cursor1, a, dest, len1); 69251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 69351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 69451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len1 == 1) { 69551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, cursor2, a, dest, len2); 69651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge 69751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 69851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 69951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 70051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparator<? super T> c = this.c; // Use local variable for performance 70151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int minGallop = this.minGallop; // " " " " " 70251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski outer: 70351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (true) { 70451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int count1 = 0; // Number of times in a row that first run won 70551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int count2 = 0; // Number of times in a row that second run won 70651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 70751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 70851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Do the straightforward thing until (if ever) one run starts 70951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * winning consistently. 71051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 71151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 71251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 1 && len2 > 0; 71351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(a[cursor2], tmp[cursor1]) < 0) { 71451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest++] = a[cursor2++]; 71551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count2++; 71651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count1 = 0; 71751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len2 == 0) 71851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 71951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 72051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest++] = tmp[cursor1++]; 72151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count1++; 72251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count2 = 0; 72351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len1 == 1) 72451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 72551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while ((count1 | count2) < minGallop); 72751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 72851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 72951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * One run is winning so consistently that galloping may be a 73051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * huge win. So try that, and continue galloping until (if ever) 73151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * neither run appears to be winning consistently anymore. 73251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 73351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 73451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 1 && len2 > 0; 73551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c); 73651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (count1 != 0) { 73751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(tmp, cursor1, a, dest, count1); 73851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski dest += count1; 73951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor1 += count1; 74051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len1 -= count1; 74151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len1 <= 1) // len1 == 1 || len1 == 0 74251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 74351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 74451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest++] = a[cursor2++]; 74551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len2 == 0) 74651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 74751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 74851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c); 74951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (count2 != 0) { 75051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, cursor2, a, dest, count2); 75151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski dest += count2; 75251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor2 += count2; 75351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len2 -= count2; 75451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len2 == 0) 75551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 75651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 75751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest++] = tmp[cursor1++]; 75851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len1 == 1) 75951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 76051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minGallop--; 76151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); 76251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (minGallop < 0) 76351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minGallop = 0; 76451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minGallop += 2; // Penalize for leaving gallop mode 76551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } // End of "outer" loop 76651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field 76751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 76851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len1 == 1) { 76951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len2 > 0; 77051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, cursor2, a, dest, len2); 77151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge 77251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else if (len1 == 0) { 77351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException( 77451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski "Comparison method violates its general contract!"); 77551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 77651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len2 == 0; 77751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 1; 77851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(tmp, cursor1, a, dest, len1); 77951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 78051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 78151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 78251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 78351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Like mergeLo, except that this method should be called only if 78451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * len1 >= len2; mergeLo should be called if len1 <= len2. (Either method 78551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * may be called if len1 == len2.) 78651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 78751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param base1 index of first element in first run to be merged 78851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param len1 length of first run to be merged (must be > 0) 78951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param base2 index of first element in second run to be merged 79051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (must be aBase + aLen) 79151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param len2 length of second run to be merged (must be > 0) 79251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 79351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void mergeHi(int base1, int len1, int base2, int len2) { 79451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 0 && len2 > 0 && base1 + len1 == base2; 79551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 79651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Copy second run into temp array 79751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T[] a = this.a; // For performance 79851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T[] tmp = ensureCapacity(len2); 799c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath int tmpBase = this.tmpBase; 800c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath System.arraycopy(a, base2, tmp, tmpBase, len2); 80151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 80251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int cursor1 = base1 + len1 - 1; // Indexes into a 803c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array 80451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int dest = base2 + len2 - 1; // Indexes into a 80551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 80651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Move last element of first run and deal with degenerate cases 80751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest--] = a[cursor1--]; 80851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len1 == 0) { 809c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); 81051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 81151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 81251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len2 == 1) { 81351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski dest -= len1; 81451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor1 -= len1; 81551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); 81651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest] = tmp[cursor2]; 81751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 81851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 81951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 82051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparator<? super T> c = this.c; // Use local variable for performance 82151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int minGallop = this.minGallop; // " " " " " 82251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski outer: 82351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (true) { 82451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int count1 = 0; // Number of times in a row that first run won 82551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int count2 = 0; // Number of times in a row that second run won 82651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 82751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 82851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Do the straightforward thing until (if ever) one run 82951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * appears to win consistently. 83051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 83151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 83251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 0 && len2 > 1; 83351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.compare(tmp[cursor2], a[cursor1]) < 0) { 83451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest--] = a[cursor1--]; 83551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count1++; 83651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count2 = 0; 83751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len1 == 0) 83851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 83951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 84051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest--] = tmp[cursor2--]; 84151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count2++; 84251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count1 = 0; 84351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len2 == 1) 84451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 84551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 84651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while ((count1 | count2) < minGallop); 84751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 84851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /* 84951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * One run is winning so consistently that galloping may be a 85051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * huge win. So try that, and continue galloping until (if ever) 85151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * neither run appears to be winning consistently anymore. 85251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 85351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 85451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 0 && len2 > 1; 85551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c); 85651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (count1 != 0) { 85751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski dest -= count1; 85851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor1 -= count1; 85951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len1 -= count1; 86051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, cursor1 + 1, a, dest + 1, count1); 86151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len1 == 0) 86251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 86351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 86451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest--] = tmp[cursor2--]; 86551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len2 == 1) 86651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 86751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 868c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c); 86951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (count2 != 0) { 87051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski dest -= count2; 87151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor2 -= count2; 87251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski len2 -= count2; 87351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2); 87451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len2 <= 1) // len2 == 1 || len2 == 0 87551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 87651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 87751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest--] = a[cursor1--]; 87851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (--len1 == 0) 87951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break outer; 88051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minGallop--; 88151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); 88251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (minGallop < 0) 88351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minGallop = 0; 88451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski minGallop += 2; // Penalize for leaving gallop mode 88551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } // End of "outer" loop 88651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field 88751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 88851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len2 == 1) { 88951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 > 0; 89051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski dest -= len1; 89151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor1 -= len1; 89251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(a, cursor1 + 1, a, dest + 1, len1); 89351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge 89451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else if (len2 == 0) { 89551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException( 89651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski "Comparison method violates its general contract!"); 89751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 89851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len1 == 0; 89951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski assert len2 > 0; 900c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); 90151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 90251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 90351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 90451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 90551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Ensures that the external array tmp has at least the specified 90651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * number of elements, increasing its size if necessary. The size 90751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * increases exponentially to ensure amortized linear time complexity. 90851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 90951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param minCapacity the minimum required capacity of the tmp array 91051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return tmp, whether or not it grew 91151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 91251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private T[] ensureCapacity(int minCapacity) { 913c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath if (tmpLen < minCapacity) { 91451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Compute smallest power of 2 > minCapacity 91551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int newSize = minCapacity; 91651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize |= newSize >> 1; 91751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize |= newSize >> 2; 91851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize |= newSize >> 4; 91951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize |= newSize >> 8; 92051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize |= newSize >> 16; 92151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize++; 92251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 92351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (newSize < 0) // Not bloody likely! 92451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize = minCapacity; 92551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 92651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newSize = Math.min(newSize, a.length >>> 1); 92751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 92851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski @SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) 929c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath T[] newArray = (T[])java.lang.reflect.Array.newInstance 930c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath (a.getClass().getComponentType(), newSize); 93151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tmp = newArray; 932c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmpLen = newSize; 933c353afc367d0bc83ac1c2bf33afb07e9ae0fbdffNarayan Kamath tmpBase = 0; 93451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 93551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return tmp; 93651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 93751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 938