Алгоритм сортировки Java

Question

Может ли кто-нибудь объяснить мне это предложение, пожалуйста?

Алгоритм сортировки представляет собой модифицированную сортировку слиянием (в которой объединение опускается, если самый высокий элемент в нижнем подсписке меньше самого низкого элемента ввысокий подсписок).

Ссылка: Arrays.sort (Object [] arr)

Я знаю, как работает Merge, но я до сих пор плохо понимаю,Спасибо.

Answer 1

Mergesort рекурсивно объединяет отсортированные подсписки.Если текущие списки, подходящие для объединения, не содержат перекрывающихся элементов, объединять их не нужно.Операция слияния будет пропущена.

Пример:

List A
1 4 8 9

List B
10 12 14 19

Нет необходимости проходить процесс сравнения этих списков, потому что 9 - это самый большой элемент из A и 10 (первый элементB) больше, чем самый большой элемент A. Результатом будет просто объединение A и B.

Все, что в документе говорится, это то, что они используют ярлык, если комплексная обработка не требуется.

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]