Implement mergesort and quicksort

def mergesort(arr):

  if len(arr) == 0:
    return []

  if len(arr) == 1:
    return arr

  p = int(len(arr) / 2)
  L = arr[0:p]
  R = arr[p:]

  L = mergesort(L)
  R = mergesort(R)

  i = 0
  j = 0
  M = []

  # Merge the sorted lists
  while i < len(L) or j < len(R):
    if i == len(L):
      M.append(R[j])
      j += 1
    elif j == len(R):
      M.append(L[i])
      i += 1
    elif L[i] < R[j]:
      M.append(L[i])
      i += 1
    else:
      M.append(R[j])
      j += 1

  return M

def quicksort(arr):
  """ This is the simple version. There is also an in-place version
  which does not need an extra storage space """

  if len(arr) == 0:
    return []

  if len(arr) == 1:
    return arr

  # First partition the arr, take last value as pivot
  p = arr[-1]
  L = []
  R = []
  for i in range(len(arr) - 1):
    if arr[i] < p:
      L.append(arr[i])
    else:
      R.append(arr[i])

  # Then recursively sort the left and righ portions
  sortedL = quicksort(L)
  sortedR = quicksort(R)
  new_arr = []
  new_arr.extend(sortedL)
  new_arr.append(p)
  new_arr.extend(sortedR)
  return new_arr

if __name__ == '__main__':
  arr = [10, 34, 2, 43, 5, 100, 12]
  print "QUICK SORT OF ", arr
  print quicksort(arr)
  print "MERGE SORT OF ", arr
  print mergesort(arr)