В чем заключается отличие быстрой сортировки от сортировки слиянием?

Отличия заключаются в подходе, реализации и производительности в разных сценариях:

1. Подход:

   • Быстрая сортировка (Quicksort) — это алгоритм "разделяй и властвуй", который работает путем выбора "опорного" элемента (pivot) и разбиения других элементов на два подмассива в зависимости от того, меньше или больше они опорного. Затем подмассивы сортируются рекурсивно.
   • Сортировка слиянием (Merge Sort) — также алгоритм "разделяй и властвуй", который делит список пополам, рекурсивно сортирует две половины, а затем сливает отсортированные половины.

2. Стабильность:

   • Быстрая сортировка не является стабильной (порядок равных элементов может измениться).
   • Сортировка слиянием является стабильной.

3. Место выполнения:

   • Быстрая сортировка обычно выполняется "на месте" (in-place), требуя минимального дополнительного пространства (за исключением пространства для стека рекурсивных вызовов).
   • Сортировка слиянием требует дополнительного пространства для временных массивов при слиянии (O(n)).

4. Производительность:

   • Средняя и лучшая сложность: O(n log n) для обоих.
   • Худшая сложность:
     • Быстрая сортировка: O(n^2) (например, при уже отсортированном или обратно отсортированном входном массиве и плохом выборе опорного элемента).
     • Сортировка слиянием: O(n log n) (всегда).
   • Влияние на производительность: В среднем, быстрая сортировка быстрее сортировки слиянием из-за лучшей производительности на практике и меньшей константы в O(n log n), хотя ее худший случай гораздо хуже.

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

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)

# пример использования
# my_list = [3, 6, 8, 10, 1, 2, 1]
# sorted_list = quicksort(my_list)
# print(sorted_list)

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

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

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# пример использования
# my_list = [3, 6, 8, 10, 1, 2, 1]
# sorted_list = merge_sort(my_list)
# print(sorted_list)