Чем отличается алгоритм быстрого сортировки от метода сортировки слиянием по принципам работы и эффективности?

Алгоритмы быстрой сортировки (QuickSort) и сортировки слиянием (MergeSort) отличаются по принципу работы и эффективности следующим образом:

• Принцип работы:

  • QuickSort — это алгоритм "разделяй и властвуй", который выбирает опорный элемент (pivot), затем переставляет элементы так, чтобы слева были меньшие, а справа — большие, и рекурсивно сортирует части.
  • MergeSort также использует "разделяй и властвуй", но делит массив пополам, рекурсивно сортирует половины, а затем сливает их в отсортированный массив.

• Сложность:

  • QuickSort в среднем работает за O(n log n), но в худшем случае — O(n²), если опорный элемент выбран неудачно.
  • MergeSort гарантирует время O(n log n) в любом случае.

• Память:

  • QuickSort обычно сортирует на месте, требует O(log n) дополнительной памяти для стека вызовов.
  • MergeSort требует дополнительную память O(n) для временных массивов при слиянии.

• Применение:

  • QuickSort часто быстрее на практике из-за меньших констант и локальности данных.
  • MergeSort стабилен (сохраняет порядок равных элементов), что важно для некоторых задач.

Пример быстрой сортировки на Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Пример сортировки слиянием:

def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)

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
    result.extend(left[i:])
    result.extend(right[j:])
    return result