java/util/TimSort.java

474         int len1 = runLen[i];
477         assert len1 > 0 && len2 > 0;
478         assert base1 + len1 == base2;
485         runLen[i] = len1 + len2;
496         int k = gallopRight(a[base2], a, base1, len1, 0, c);
499         len1 -= k;
500         if (len1 == 0)
507         len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
512         // Merge remaining runs, using tmp array with min(len1, len2) elements
513         if (len1 <= len2)
514             mergeLo(base1, len1, base2, len2);
516             mergeHi(base1, len1, base2, len2);
669      * (a[base1 + len1-1]) must be greater than all elements of the second run.
671      * For performance, this method should be called only when len1 <= len2;
672      * its twin, mergeHi should be called if len1 >= len2.  (Either method
673      * may be called if len1 == len2.)
676      * @param len1  length of first run to be merged (must be > 0)
681     private void mergeLo(int base1, int len1, int base2, int len2) {
682         assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
686         T[] tmp = ensureCapacity(len1);
690         System.arraycopy(a, base1, tmp, cursor1, len1);
695             System.arraycopy(tmp, cursor1, a, dest, len1);
698         if (len1 == 1) {
716                 assert len1 > 1 && len2 > 0;
727                     if (--len1 == 1)
738                 assert len1 > 1 && len2 > 0;
739                 count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
744                     len1 -= count1;
745                     if (len1 <= 1) // len1 == 1 || len1 == 0
762                 if (--len1 == 1)
772         if (len1 == 1) {
776         } else if (len1 == 0) {
781             assert len1 > 1;
782             System.arraycopy(tmp, cursor1, a, dest, len1);
788      * len1 >= len2; mergeLo should be called if len1 <= len2.  (Either method
789      * may be called if len1 == len2.)
792      * @param len1  length of first run to be merged (must be > 0)
797     private void mergeHi(int base1, int len1, int base2, int len2) {
798         assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
806         int cursor1 = base1 + len1 - 1;  // Indexes into a
812         if (--len1 == 0) {
817             dest -= len1;
818             cursor1 -= len1;
819             System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
836                 assert len1 > 0 && len2 > 1;
841                     if (--len1 == 0)
858                 assert len1 > 0 && len2 > 1;
859                 count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
863                     len1 -= count1;
865                     if (len1 == 0)
882                 if (--len1 == 0)
893             assert len1 > 0;
894             dest -= len1;
895             cursor1 -= len1;
896             System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
902             assert len1 == 0;