Implementing Merge Sort in Python

Merge Sort

Merge sort is a popular example for divide and conquer algorithm. Divide the lists and merge it back in sorted order. Check out the wikipedia if you haven’t seen it before, it’s cool:

The basic idea of the algorithm is as follow:

  • Given list of numbers, divide into sublist until we have n number of list that contain 1 number each
  • Repeatedly merge the two sublists together until we obtain sorted list

The solution in python is as below:

def merge_sort(nums):
  if len(nums) <= 1:
    return nums
  mid = len(nums)/2
  left = merge_sort(nums[:mid])
  right = merge_sort(nums[mid:])
  return merge(left, right)

def merge(left, right):
  if not left:
    return right
  if not right:
    return left
  if left[0] < right[0]:
    return [left[0]] + merge(left[1:], right)
  return [right[0]] + merge(left, right[1:])

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s