We all know that a Merge Sort is a sorting algorithm. You can find the implementation code of this algorithm is everywhere. But I want to organize this on my site.
The complexity of this algorithm.
Worst Complexity: n*log(n)
Average Complexity: n*log(n)
Best Complexity: n*log(n)
Space Complexity: n
def merge_sort(lst): if len(lst) > 1: mid = len(lst) // 2 left = lst[:mid] right = lst[mid:] merge_sort(left) merge_sort(right) i = 0 j = 0 k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: lst[k] = left[i] i += 1 else: lst[k] = right[j] j += 1 k += 1 while i < len(left): lst[k] = left[i] i += 1 k += 1 while j < len(right): lst[k] = right[j] j += 1 k += 1 return lst sorted = merge_sort([7, 5, 4, 2, 6, 1, 3]) # Output = [1, 2, 3, 4, 5, 6, 7] print(sorted)