Сортировка слиянием в Python
Данные рекурсивно делятся, затем отсортированные части сливаются.
Что такое Сортировка слиянием в Python?
Данные рекурсивно делятся, затем отсортированные части сливаются.
Сортируйте методом разделяй и властвуй.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Визуализация: Сортировка слиянием в Python
O(n log n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
main.py
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))Ожидаемый результат
[3, 9, 10, 27, 38, 43, 82]Как это работает
Гарантируется время O(n log n), требуется O(n) дополнительной памяти.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.