Merge Sort Implementation in Python

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)
Scroll to Top