| 2802 | /// |
| 2803 | /// - `end`: the end index + 1 |
| 2804 | @SuppressWarnings("unchecked") |
| 2805 | private static void mergeSort(Object[] in, Object[] out, int start, |
| 2806 | int end) { |
| 2807 | int len = end - start; |
| 2808 | // use insertion sort for small arrays |
| 2809 | if (len <= SIMPLE_LENGTH) { |
| 2810 | for (int i = start + 1; i < end; i++) { |
| 2811 | java.lang.Comparable<Object> current = |
| 2812 | (java.lang.Comparable<Object>) out[i]; |
| 2813 | Object prev = out[i - 1]; |
| 2814 | if (current.compareTo(prev) < 0) { |
| 2815 | int j = i; |
| 2816 | do { |
| 2817 | out[j--] = prev; |
| 2818 | } while (j > start |
| 2819 | && current.compareTo(prev = out[j - 1]) < 0); |
| 2820 | out[j] = current; |
| 2821 | } |
| 2822 | } |
| 2823 | return; |
| 2824 | } |
| 2825 | int med = (end + start) >>> 1; |
| 2826 | mergeSort(out, in, start, med); |
| 2827 | mergeSort(out, in, med, end); |
| 2828 | |
| 2829 | // merging |
| 2830 | |
| 2831 | // if arrays are already sorted - no merge |
| 2832 | if (((java.lang.Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) { |
| 2833 | System.arraycopy(in, start, out, start, len); |
| 2834 | return; |
| 2835 | } |
| 2836 | int r = med, i = start; |
| 2837 | |
| 2838 | // use merging with exponential search |
| 2839 | do { |
| 2840 | java.lang.Comparable<Object> fromVal = (java.lang.Comparable<Object>) in[start]; |
| 2841 | java.lang.Comparable<Object> rVal = (java.lang.Comparable<Object>) in[r]; |
| 2842 | if (fromVal.compareTo(rVal) <= 0) { |
| 2843 | int l_1 = find(in, rVal, -1, start + 1, med - 1); |
| 2844 | int toCopy = l_1 - start + 1; |
| 2845 | System.arraycopy(in, start, out, i, toCopy); |
| 2846 | i += toCopy; |
| 2847 | out[i++] = rVal; |
| 2848 | r++; |
| 2849 | start = l_1 + 1; |
| 2850 | } else { |
| 2851 | int r_1 = find(in, fromVal, 0, r + 1, end - 1); |
| 2852 | int toCopy = r_1 - r + 1; |
| 2853 | System.arraycopy(in, r, out, i, toCopy); |
| 2854 | i += toCopy; |
| 2855 | out[i++] = fromVal; |
| 2856 | start++; |
| 2857 | r = r_1 + 1; |
| 2858 | } |
| 2859 | } while ((end - r) > 0 && (med - start) > 0); |
| 2860 | |
| 2861 | // copy rest of array |