1 /* 2 * Copyright (c) 2009, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.java2d.marlin; 27 28 /** 29 * MergeSort adapted from (OpenJDK 8) java.util.Array.legacyMergeSort(Object[]) 30 * to swap two arrays at the same time (x & y) 31 * and use external auxiliary storage for temporary arrays 32 */ 33 final class MergeSort { 34 35 // insertion sort threshold 36 public static final int INSERTION_SORT_THRESHOLD = 14; 37 38 /** 39 * Modified merge sort: 40 * Input arrays are in both auxX/auxY (sorted: 0 to insertionSortIndex) 41 * and x/y (unsorted: insertionSortIndex to toIndex) 42 * Outputs are stored in x/y arrays 43 */ mergeSortNoCopy(final int[] x, final int[] y, final int[] auxX, final int[] auxY, final int toIndex, final int insertionSortIndex)44 static void mergeSortNoCopy(final int[] x, final int[] y, 45 final int[] auxX, final int[] auxY, 46 final int toIndex, 47 final int insertionSortIndex) 48 { 49 if ((toIndex > x.length) || (toIndex > y.length) 50 || (toIndex > auxX.length) || (toIndex > auxY.length)) { 51 // explicit check to avoid bound checks within hot loops (below): 52 throw new ArrayIndexOutOfBoundsException("bad arguments: toIndex=" 53 + toIndex); 54 } 55 56 // sort second part only using merge / insertion sort 57 // in auxiliary storage (auxX/auxY) 58 mergeSort(x, y, x, auxX, y, auxY, insertionSortIndex, toIndex); 59 60 // final pass to merge both 61 // Merge sorted parts (auxX/auxY) into x/y arrays 62 if ((insertionSortIndex == 0) 63 || (auxX[insertionSortIndex - 1] <= auxX[insertionSortIndex])) { 64 // 34 occurences 65 // no initial left part or both sublists (auxX, auxY) are sorted: 66 // copy back data into (x, y): 67 System.arraycopy(auxX, 0, x, 0, toIndex); 68 System.arraycopy(auxY, 0, y, 0, toIndex); 69 return; 70 } 71 72 for (int i = 0, p = 0, q = insertionSortIndex; i < toIndex; i++) { 73 if ((q >= toIndex) || ((p < insertionSortIndex) 74 && (auxX[p] <= auxX[q]))) { 75 x[i] = auxX[p]; 76 y[i] = auxY[p]; 77 p++; 78 } else { 79 x[i] = auxX[q]; 80 y[i] = auxY[q]; 81 q++; 82 } 83 } 84 } 85 86 /** 87 * Src is the source array that starts at index 0 88 * Dest is the (possibly larger) array destination with a possible offset 89 * low is the index in dest to start sorting 90 * high is the end index in dest to end sorting 91 */ mergeSort(final int[] refX, final int[] refY, final int[] srcX, final int[] dstX, final int[] srcY, final int[] dstY, final int low, final int high)92 private static void mergeSort(final int[] refX, final int[] refY, 93 final int[] srcX, final int[] dstX, 94 final int[] srcY, final int[] dstY, 95 final int low, final int high) 96 { 97 final int length = high - low; 98 99 /* 100 * Tuning parameter: list size at or below which insertion sort 101 * will be used in preference to mergesort. 102 */ 103 if (length <= INSERTION_SORT_THRESHOLD) { 104 // Insertion sort on smallest arrays 105 dstX[low] = refX[low]; 106 dstY[low] = refY[low]; 107 108 for (int i = low + 1, j = low, x, y; i < high; j = i++) { 109 x = refX[i]; 110 y = refY[i]; 111 112 while (dstX[j] > x) { 113 // swap element 114 dstX[j + 1] = dstX[j]; 115 dstY[j + 1] = dstY[j]; 116 if (j-- == low) { 117 break; 118 } 119 } 120 dstX[j + 1] = x; 121 dstY[j + 1] = y; 122 } 123 return; 124 } 125 126 // Recursively sort halves of dest into src 127 128 // note: use signed shift (not >>>) for performance 129 // as indices are small enough to exceed Integer.MAX_VALUE 130 final int mid = (low + high) >> 1; 131 132 mergeSort(refX, refY, dstX, srcX, dstY, srcY, low, mid); 133 mergeSort(refX, refY, dstX, srcX, dstY, srcY, mid, high); 134 135 // If arrays are inverted ie all(A) > all(B) do swap A and B to dst 136 if (srcX[high - 1] <= srcX[low]) { 137 // 1561 occurences 138 final int left = mid - low; 139 final int right = high - mid; 140 final int off = (left != right) ? 1 : 0; 141 // swap parts: 142 System.arraycopy(srcX, low, dstX, mid + off, left); 143 System.arraycopy(srcX, mid, dstX, low, right); 144 System.arraycopy(srcY, low, dstY, mid + off, left); 145 System.arraycopy(srcY, mid, dstY, low, right); 146 return; 147 } 148 149 // If arrays are already sorted, just copy from src to dest. This is an 150 // optimization that results in faster sorts for nearly ordered lists. 151 if (srcX[mid - 1] <= srcX[mid]) { 152 // 14 occurences 153 System.arraycopy(srcX, low, dstX, low, length); 154 System.arraycopy(srcY, low, dstY, low, length); 155 return; 156 } 157 158 // Merge sorted halves (now in src) into dest 159 for (int i = low, p = low, q = mid; i < high; i++) { 160 if ((q >= high) || ((p < mid) && (srcX[p] <= srcX[q]))) { 161 dstX[i] = srcX[p]; 162 dstY[i] = srcY[p]; 163 p++; 164 } else { 165 dstX[i] = srcX[q]; 166 dstY[i] = srcY[q]; 167 q++; 168 } 169 } 170 } 171 MergeSort()172 private MergeSort() { 173 } 174 } 175