def merge(arr, l, m, r):
  l_length = (m - l) + 1
  r_length = r - m

  left_half = [0]*l_length
  right_half = [0]*r_length

  for i in range(0 , l_length):
    left_half[i] = arr[l + i]

  for j in range(0 , r_length):
    right_half[j] = arr[m + 1 + j]

  i = 0
  j = 0
  k = l

  while i < l_length and j < r_length :

    if left_half[i] <= right_half[j]:
      arr[k] = left_half[i]
      i += 1
    else:
      arr[k] = right_half[j]
      j += 1
    k += 1

  while i < l_length:
    arr[k] = left_half[i]
    i += 1
    k += 1


  while j < r_length:
    arr[k] = right_half[j]
    j += 1
    k += 1
  return arr

def merge_sort_helper(arr,l,r):
  if l < r:

    m = (l+(r-1))//2
    merge_sort_helper(arr, l, m)
    merge_sort_helper(arr, m+1, r)

    return merge(arr, l, m, r)
  else:
    return arr

def mergeSort(arr):
  return merge_sort_helper( arr, 0, len(arr)-1 )