Алгоритмы сортировки — классика computer science и обязательная тема технических интервью. Но важнее теории — понимание, почему они работают именно так, и когда какой применить на практике.

Сложность алгоритмов: Big O

Big O описывает, как растёт время выполнения при росте входных данных. O(n²) при n=1000 даёт 1 000 000 операций. O(n log n) — около 10 000. Разница критическая для больших данных.

Пузырьковая сортировка O(n²)

# bubble_sort.py
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break  # оптимизация: уже отсортировано
    return arr

Сортировка слиянием (Merge Sort) O(n log n)

# merge_sort.py
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)

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
    return result + left[i:] + right[j:]

// Когда какой алгоритм использовать

Маленькие данные (<50): insertion sort. Данные почти отсортированы: bubble/insertion. Нужна стабильность (сохранять порядок равных): merge sort. Общий случай, скорость: quicksort. На практике: используйте встроенную sort() — в Python это Timsort O(n log n) с отличной константой.

QuickSort O(n log n) средний

# quicksort.py
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quicksort(left) + mid + quicksort(right)
Python код алгоритмов