Сортировка стала проще: изучение различных методов сортировки слиянием в Python

Сортировка — фундаментальная операция в информатике. За прошедшие годы были разработаны различные алгоритмы сортировки для эффективной организации данных. Сортировка слиянием — один из таких алгоритмов, который следует парадигме «разделяй и властвуй». В этой статье блога мы погрузимся в мир сортировки слиянием и рассмотрим различные методы ее реализации в 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 iterative_merge_sort(arr):
    n = len(arr)
    width = 1

    while width < n:
        for i in range(0, n, width * 2):
            left = arr[i:i+width]
            right = arr[i+width:i+width*2]

            arr[i:i+width*2] = merge(left, right)

        width *= 2

    return arr

Метод 3: сортировка слиянием на месте

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

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

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    in_place_merge_sort(left_half)
    in_place_merge_sort(right_half)

    merge_in_place(arr, left_half, right_half)

    return arr
def merge_in_place(arr, left, right):
    i = j = k = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

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

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