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])
(collection: list)
| 11 | |
| 12 | |
| 13 | def merge_sort(collection: list) -> list: |
| 14 | """ |
| 15 | Sorts a list using the merge sort algorithm. |
| 16 | |
| 17 | :param collection: A mutable ordered collection with comparable items. |
| 18 | :return: The same collection ordered in ascending order. |
| 19 | |
| 20 | Time Complexity: O(n log n) |
| 21 | Space Complexity: O(n) |
| 22 | |
| 23 | Examples: |
| 24 | >>> merge_sort([0, 5, 3, 2, 2]) |
| 25 | [0, 2, 2, 3, 5] |
| 26 | >>> merge_sort([]) |
| 27 | [] |
| 28 | >>> merge_sort([-2, -5, -45]) |
| 29 | [-45, -5, -2] |
| 30 | """ |
| 31 | |
| 32 | def merge(left: list, right: list) -> list: |
| 33 | """ |
| 34 | Merge two sorted lists into a single sorted list. |
| 35 | |
| 36 | :param left: Left collection |
| 37 | :param right: Right collection |
| 38 | :return: Merged result |
| 39 | """ |
| 40 | result = [] |
| 41 | while left and right: |
| 42 | result.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) |
| 43 | result.extend(left) |
| 44 | result.extend(right) |
| 45 | return result |
| 46 | |
| 47 | if len(collection) <= 1: |
| 48 | return collection |
| 49 | mid_index = len(collection) // 2 |
| 50 | return merge(merge_sort(collection[:mid_index]), merge_sort(collection[mid_index:])) |
| 51 | |
| 52 | |
| 53 | if __name__ == "__main__": |