Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 <p>Алгоритм<strong>сортировки слиянием</strong>относят к алгоритмам, работающим по принципу "разделяй и властвуй". Он разбивает список на 2 части, каждую разбивает ещё на 2 и так далее, пока не останутся единичные элементы. В результате соседние элементы становятся сортированными парами. Потом эти пары объединяют и сортируют с другими парами. Процесс продолжается, пока не отсортируются все элементы.</p>

2 <h2>Особенности работы</h2>

3 <p>Список рекурсивно разделяется пополам, пока не получатся списки размером в 1 элемент. Массив, состоящий из одного элемента, считают упорядоченным. Соседние элементы сравнивают и соединяют вместе до тех пор, пока не сформируется полный отсортированный список.</p>

4 <p>Сортировка выполняется путём сравнения наименьших элементов каждого подмассива. При этом первые элементы каждого подмассива сравниваются первыми. Самый маленький элемент перемещается в результирующий массив, а счётчики результирующего массива и подмассива, где взяли элемент, увеличиваются на один.</p>

5 <h2>Реализация на "Пайтон"</h2>

6 <p>Алгоритм реализуется следующим образом:</p>

7 def merge(left_list, right_list): sorted_list = [] left_list_index = right_list_index = 0 # Т. к. длина списков применяется часто, создадим для удобства переменные left_list_length, right_list_length = len(left_list), len(right_list) for _ in range(left_list_length + right_list_length): if left_list_index < left_list_length and right_list_index < right_list_length: # Сравниваем первые элементы в начале каждого списка # Если 1-й элемент левого подсписка меньше, добавляем его # в сортированный массив if left_list[left_list_index] <= right_list[right_list_index]: sorted_list.append(left_list[left_list_index]) left_list_index += 1 # Если 1-й элемент правого подсписка меньше, добавляем его # в сортированный массив else: sorted_list.append(right_list[right_list_index]) right_list_index += 1 # Когда достигнут конец левого списка, добавляем элементы правого списка # в конец результирующего списка elif left_list_index == left_list_length: sorted_list.append(right_list[right_list_index]) right_list_index += 1 # Когда достигнут конец правого списка, добавляем элементы левого списка # в сортированный массив elif right_list_index == right_list_length: sorted_list.append(left_list[left_list_index]) left_list_index += 1 return sorted_list def merge_sort(nums): # Возвращаем список, когда он состоит из одного элемента if len(nums) <= 1: return nums # Чтобы найти середину списка, применяем деление без остатка # Индексы должны быть integer mid = len(nums) // 2 # Сортируем и объединяем подсписки left_list = merge_sort(nums[:mid]) right_list = merge_sort(nums[mid:]) # Объединяем сортированные списки в результирующий return merge(left_list, right_list) # Проверяем, что всё работает random_list_of_nums = [120, 45, 68, 250, 176] random_list_of_nums = merge_sort(random_list_of_nums) print(random_list_of_nums)<p>Здесь следует отметить, что функция merge_sort() возвращает новый список, а не сортирует существующий. Именно поэтому<strong>сортировка слиянием требует больше памяти</strong>, чем, к примеру, алгоритмы сортировки выборкой и вставками, алгоритмы пирамидальной и пузырьковой сортировки. Память необходима для создания нового списка такого же размера, что и входной список.</p>

8 <h2>Время сортировки</h2>

9 <p>Как правило, время сортировки слиянием составляет O(n log n).</p>

10 <p><em><a>Источник</a></em></p>