/
ssmih
/
Python
Обзор
Документация
Войти
/
ssmih
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
sorts/merge_sort.py
64 строки
2 KB
Abhijit Kumar Singh
Specify space complexity for merge sort (#11749)
30 авг 2025, 03:37
Не верифицирован
30 авг 2025, 03:37
1e0d317
Код
Авторство
О чём код?
""" This is a pure Python implementation of the merge sort algorithm. For doctests run following command: python -m doctest -v merge_sort.py or python3 -m doctest -v merge_sort.py For manual testing run: python merge_sort.py """ def merge_sort(collection: list) -> list: """ Sorts a list using the merge sort algorithm. :param collection: A mutable ordered collection with comparable items. :return: The same collection ordered in ascending order. Time Complexity: O(n log n) Space Complexity: O(n) Examples: >>> merge_sort([0, 5, 3, 2, 2]) [0, 2, 2, 3, 5] >>> merge_sort([]) [] >>> merge_sort([-2, -5, -45]) [-45, -5, -2] """ def merge(left: list, right: list) -> list: """ Merge two sorted lists into a single sorted list. :param left: Left collection :param right: Right collection :return: Merged result """ result = [] while left and right: result.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) result.extend(left) result.extend(right) return result if len(collection) <= 1: return collection mid_index = len(collection) // 2 return merge(merge_sort(collection[:mid_index]), merge_sort(collection[mid_index:])) if __name__ == "__main__": import doctest doctest.testmod() try: user_input = input("Enter numbers separated by a comma:\n").strip() unsorted = [int(item) for item in user_input.split(",")] sorted_list = merge_sort(unsorted) print(*sorted_list, sep=",") except ValueError: print("Invalid input. Please enter valid integers separated by commas.")