Java排序算法

Question

请问有人能解释一下这个句子吗？

排序算法是改进的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。

链接：Arrays.sort(Object[] arr)

我知道如何使用归并排序，但我仍然不太理解。谢谢。

- Fulano

Answer 1

Mergesort是一种递归地合并已排序子列表的算法。如果当前可合并的子列表不含重叠元素，则无需进行合并操作，可以直接跳过。

示例：

List A
1 4 8 9

List B
10 12 14 19

不需要比较这些列表，因为9是A的最大元素，而10（B的第一个元素）比A的最大元素更大。结果只是A和B的连接。

文档所说的就是如果不需要全面处理，则采用快捷方式。

- Jonathon Faust

Answer 2

假设您正在执行归并排序，并且即将合并两个已排序的子列表[1, 3, 4]和[2, 5, 6]。然后，您必须运行合并算法以将这两个半部分交错成整体[1, 2, 3, 4, 5, 6]。

[1] + [2] + [3, 4] + [5, 6] = [1, 2, 3, 4, 5, 6]

但假设在您排序了两个子列表之后，您有[1, 2, 3]和[4, 5, 6]。低子列表中的最高元素（3）小于高子列表中的最低元素（4）。不需要合并这两个子列表；您可以简单地将它们连接在一起。

[1, 2, 3] + [4, 5, 6] = [1, 2, 3, 4, 5, 6]

- John Kugelman