Merge sort in Python

Problem

Implement merge sort algorithm in Python.

Solution

For definition and explanation, You may refer to the following post. This post is just a rewrite in Python.

Before jumping directly to the code, check out the following nice YouTube clip

Recursive merge sort in python

Take a look at the comments for explanation...

# Merge sort function receives 
# a list and an index number
def MergeSort(A, n):

	# If the list contains one number
	# then it is already sorted
	if (n == 1):
		return A
	else:
		# Calculate the position 
		# of the middle number
		m = n/2

		# Create two lists. Copy the 
		# first half to a and the 
		# second half to b
		a = A[:m]
		b = A[m:]

		# Recursively call the 
		# function on the two halves
		a = MergeSort(a, m)
		b = MergeSort(b, n-m)
		
		# The rest of the code is to 
		# merge the sorted halves
		l = 0
		r = 0
		k = 0

		while (l < m and r < n-m):
			# If the number from the first half
			# is less than the number from the
			# second half then push it to the result
			if (a[l] <= b[r]):
				A[k] = a[l]            
				l+=1
			 
			# Otherwise push the number from the
			# second half       
			else:		    
				A[k] = b[r]            
				r+=1	
			k+=1
		

		# If the loop above is finished and still
		# l is less than m then this means there
		# are numbers in the first half that
		# need to be appended to the result
		if (l < m):
			while (l < m):
				A[k] = a[l]
				l+=1
				k+=1
			
		# Similarly we need to append those numbers
		# in the second half that were not added
		if (r < n-m):
			while( r < n-m):
				A[k] = b[r]
				r+=1
				k+=1

		# Return the sorted list
		return A
	
# Example list
A = [4, 2, 1, 0, -1]

# Sort list
res = MergeSort(A, len(A))

# Print result
print(res)

Thanks for reading. For questions, please use the comments section below

Leave a Reply