November 20, 2017

# 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