Merge Sort

mergeSort.py

# This approach does not sort nums in place

def merge(numsLeft, numsRight):

  result = []
  i = 0
  j = 0
  while i < len(numsLeft) and j < len(numsRight):
    if numsLeft[i] <= numsRight[j]:
      result.append(numsLeft[i])
      i += 1
    else:
      result.append(numsRight[j])
      j += 1

  while i < len(numsLeft):
    result.append(numsLeft[i])
    i += 1
  while j < len(numsRight):
    result.append(numsRight[j])
    j += 1

  return result
   
def mergeSortH(nums, l, r):

  if l == r:
    return [nums[l]]

  m = l + (r-l)/2

  L = mergeSortH(nums, l, m)
  R = mergeSortH(nums, m + 1, r)

  return merge(L,R)

def mergeSort(nums):
  return mergeSortH(nums, 0, len(nums) - 1)

nums = [5, 3, 8, 6, 2, 1, 0, 9, 7, 4]

print nums
print mergeSort(nums)