Сортировка — фундаментальная операция в информатике, а сортировка слиянием — популярный алгоритм сортировки, известный своей эффективностью и простотой. В этой статье мы рассмотрим различные методы реализации сортировки слиянием в Python, а также приведем примеры кода. Независимо от того, являетесь ли вы новичком или опытным программистом, эта статья предоставит вам полное представление о различных подходах к реализации сортировки слиянием.

Метод 1: рекурсивный подход
Рекурсивный подход — наиболее распространенный и интуитивно понятный способ реализации сортировки слиянием. Он следует парадигме «разделяй и властвуй», когда входной массив многократно делится на две половины, пока каждый подмассив не будет содержать только один элемент. Затем подмассивы объединяются в отсортированном виде.

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 = 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

Метод 2: итеративный подход
Хотя рекурсивная реализация элегантна, она может быть не самой эффективной из-за накладных расходов на вызовы функций. В качестве альтернативы мы можем реализовать сортировку слиянием итеративно, используя восходящий подход.

def merge_sort(arr):
    current_size = 1
    while current_size < len(arr) - 1:
        left = 0
        while left < len(arr) - 1:
            mid = min((left + current_size - 1), (len(arr) - 1))
            right = ((2 * current_size + left - 1, len(arr) - 1)[2 * current_size + left - 1 > len(arr) - 1])
            merge(arr, left, mid, right)
            left = left + current_size * 2
        current_size = 2 * current_size
def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = arr[left + i]
    for i in range(0, n2):
        R[i] = arr[mid + i + 1]
    i = j = 0
    k = left
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

Метод 3: сортировка слиянием на месте
В предыдущих методах мы создавали новые массивы в процессе слияния. Однако можно выполнить сортировку слиянием на месте, то есть сортировка выполняется непосредственно в исходном массиве без использования дополнительного пространства.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

Сортировка слиянием — это эффективный алгоритм сортировки, гарантирующий временную сложность O(n log n). В этой статье мы рассмотрели три различных метода реализации сортировки слиянием в Python: рекурсивный подход, итеративный подход и подход на месте. Каждый метод имеет свои преимущества и может подходить для разных сценариев. Поняв эти реализации, вы сможете выбрать наиболее подходящую для ваших конкретных нужд.