Раскройте возможности сортировки слиянием в Python с помощью нашего подробного руководства. Погрузитесь глубже в его работу и преимущества, а также познакомьтесь с практической реализацией Python. Идеально подходит как для новичков, так и для профессионалов. Повысьте свои навыки алгоритма сегодня!

1. Введение

Когда дело доходит до алгоритмов сортировки, сортировка слиянием выделяется своей эффективностью и широким применением. Готовитесь ли вы к собеседованию, проекту или просто любопытствуете, это руководство углубляет понимание и реализацию сортировки слиянием в Python.

2. Что такое сортировка слиянием?

2.1. Определение:

Сортировка слиянием — это алгоритм «разделяй и властвуй», который работает путем рекурсивного разделения списка пополам. Если у вас есть несколько списков, каждый из которых состоит из одного элемента, вы объединяете их обратно таким образом, чтобы они были отсортированы.

2.2. Преимущества:

  • Стабильная сортировка. Исходный порядок сохраняется для равных элементов.
  • Временная сложность: O(nlogn) во всех трех случаях (худшем, среднем и лучшем), что обеспечивает предсказуемость.

3. Как работает сортировка слиянием?

Пошаговый процесс:

  1. Разделить. Разделить несортированный список на n подсписков, каждый из которых содержит один элемент (список из одного элемента считается отсортированным).
  2. Завоевать. Повторно объединяйте подсписки для создания новых отсортированных подсписков, пока не останется только один подсписок.

4. Реализация сортировки слиянием в Python

Давайте посмотрим на реализацию сортировки слиянием на Python:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

# Splitting the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    # Recursively sorting both halves
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
    # Merging the sorted halves
    return merge(left_sorted, right_sorted)
def merge(left, right):
    merged = []
    left_index, right_index = 0, 0
    # Sorting elements and adding to the merged list
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]…