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…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
# 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