Arrays 在对 Object 数组进行排序是会使用到 legacyMergeSort 和 ComparableTimSort.sort
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
其中 legacyMergeSort 调用的就是 mergeSort 方法
- legacyMergeSort(Object[] a): 需要配置 java.util.Arrays.useLegacyMergeSort == true, 代码注释说会在以后的发行版本中移除 legacyMergeSort 方法
/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
来看看 mergeSort 的具体实现。
- 当 array.length < 7 时会使用插入排序(insertion sort)
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
迭代的时候每次都选择当前 index 后面最大的元素进行交互位置
- 完整的 mergeSort() 实现
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
以一个 length 为 16 的数组举例,大致解释一下 mergeSort 排序:
调用 mergeSort 方法时 length 为 16, 因为 length 为 8 不满足插入排序的条件， 此时将数组分为两半:
数组1的 index 范围为: [0, 8)
数组2的 index 范围为: [8, 16)
继续看数组1: 对数组以递归调用, 因为 length 为 8 不满足插入排序的条件，此时将数组1分为 2 半:
数组1_1, index 范围为: [0, 4)
此时满足 length < 7 的条件, 进行插入排序
数组1_2, index 范围为: [4, 8)
此时也满足 length < 7 的条件, 进行插入排序
此时 数组1_1 和 数组1_2 都是局部有序的, 然后下一步会判断 数组1_1 的最大值与 数组1_2 的最小值之间的关系, 如果 max(数组1_1) <= min(数组1_2) 则说明 数组1_1 + 数组1_2 也是有序的的,
否则对 数组1_1 和 数组1_2 进行2-路归并排序，最终得到的结果是 数组 index 为[0, 8) 的数据都是有序的
对数组2 进行两次递归调用后，数组 index 为[8, 16) 的数据都是有序的，判断数组1 的最大值和数组2 的最小值之间的关系, 如果 max(数组1) <= min(数组2)，则说明 数组1 + 数组2 也是有序的的,
否则对 数组1 和 数组2 进行 2-路归并排序得到最终结果
以上就是 mergeSort 排序的全部过程了
