Какие знаешь алгоритмы сортировки

В Python популярны несколько алгоритмов сортировки, каждый с разной сложностью и применением:

1. Сортировка пузырьком (Bubble Sort)
   Простой, но неэффективный (O(n²)).
   python

   Копировать

   def bubble_sort(arr):
       n = len(arr)
       for i in range(n):
           for j in range(0, n-i-1):
               if arr[j] > arr[j+1]:
                   arr[j], arr[j+1] = arr[j+1], arr[j]

2. Быстрая сортировка (Quick Sort)
   Рекурсивный, в среднем O(n log n).

   python

   Копировать

   def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

3. Сортировка слиянием (Merge Sort)
   Устойчивый, O(n log n), но требует доп. памяти.

   python

   Копировать

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

4. Timsort (встроенный в Python)
   Гибридный (слияние + вставки), O(n log n) в худшем случае. Используется в sorted() и list.sort().

Для небольших данных подойдут простые методы, для больших — Quick Sort или Timsort.