Implementation of Merge Sort in Python
Merge Sort In sorting n objects, merge sort has an average and worst-case performance of O(n log n).
Merge sort is a stable sort in the most implementations. The most common implementation does not sort in place, meaning it requires extra space.
Implementation in Python from typing import List # Python merge sort implementation # Time complexity: O(NlogN), space complexity: O(N) def merge_sort(nums: List[int]): # Base case if len(nums) <= 1: return nums mid = len(nums) // 2 left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:]) return merge(left, right) def merge(left: List[int], right: List[int]): i, j = 0, 0 res = [] # Compare the elements in the left and right list and append the smaller one to the result list while i < len(left) and j < len(right): if left[i] <= right[j]: res.