Что хотят услышать интервьюеры:

Нужно показать знание базовых алгоритмов сортировки, их идеи, сложность и когда их уместно применять. В Python также важно понимать, что встроенная сортировка обычно лучше ручной реализации для прикладных задач. Хорошо, если упомянуты стабильность сортировки и разница между in-place и не in-place подходами.

Определение:

Сортировка данных — это упорядочивание элементов по заданному критерию, например по возрастанию, убыванию или по ключу. Основные методы сортировки обычно делят на простые учебные алгоритмы и более эффективные практические подходы.

К основным алгоритмам относятся:

Bubble Sort — меняет местами соседние элементы, пока массив не станет отсортирован.
Selection Sort — находит минимальный элемент и ставит его в начало.
Insertion Sort — по одному вставляет элементы в уже отсортированную часть.
Merge Sort — делит массив пополам, сортирует части и затем объединяет.
Quick Sort — выбирает опорный элемент и разделяет массив на две части.
Heap Sort — строит кучу и последовательно извлекает максимум или минимум.
Timsort — гибридный алгоритм, который используется во встроенной сортировке Python.

Пример использования:

data = [5, 2, 9, 1, 5, 6]

# Встроенная сортировка Python
sorted_data = sorted(data)

# Сортировка на месте
data.sort()

# Сортировка по ключу
people = [
    {"name": "Alice", "age": 30},
    {"name": "Bob", "age": 25},
    {"name": "Eve", "age": 35},
]

sorted_people = sorted(people, key=lambda x: x["age"])

Пояснение кода:

Здесь показаны три типичных сценария сортировки в Python.

sorted(data) возвращает новый отсортированный список, не изменяя исходный.
data.sort() сортирует сам список на месте.
sorted(..., key=...) позволяет сортировать не сами объекты, а значение, которое из них вычисляется, например возраст.

Если говорить про алгоритмы, то на практике в Python обычно не пишут Bubble Sort или Quick Sort вручную, потому что встроенная сортировка уже оптимизирована.

Ключевые моменты:

Для собеседования важно знать не только названия, но и базовую идею каждого алгоритма.
Bubble, Selection, Insertion — простые, но обычно медленные на больших данных.
Merge Sort обычно дает O(n log n) и сохраняет стабильность.
Quick Sort в среднем быстрый, но в худшем случае может деградировать.
В Python встроенная сортировка основана на Timsort и обычно предпочтительнее ручной реализации.
Полезно помнить разницу между сортировкой на месте и созданием нового списка.

Можешь перечислить основные методы сортировки данных, которые ты знаешь?