Merge Sort Python

Сортировка слиянием (merge sort) является одним из наиболее эффективных алгоритмов сортировки, основан на принципе "разделяй и властвуй".

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

Пример реализации merge sort на языке Python:

python
def merge_sort(arr):
    # Проверка на базовый случай, когда список состоит из одного элемента
    if len(arr) <= 1:
        return arr
    # Рекурсивно разделяем список пополам
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    # Рекурсивный вызов сортировки для обеих половинок
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    # Объединяем отсортированные половинки
    return merge(left_half, right_half)
def merge(left, right):
    result = []
    i = 0
    j = 0
    # Сравниваем элементы левой и правой половинок и добавляем их в результат по возрастанию
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # Добавляем остаток элементов из левой или правой половинки
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result
# Пример использования
arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # Вывод: [17, 20, 26, 31, 44, 54, 55, 77, 93]

В данном примере функция merge_sort разделяет список пополам, затем рекурсивно вызывает себя для сортировки обеих половинок. Функция merge осуществляет процесс слияния двух отсортированных половинок в один отсортированный список. Результирующий отсортированный список возвращается из функции merge_sort и выводится на экран.