def msort(li):
  match li:
    case []: return []
    case [x]: return [x]
    case xs: 
      ys, zs = halve(xs)
      return merge(msort(ys), msort(zs))
     
def halve(xs):
  ys = xs[:len(xs) // 2]
  zs = xs[len(xs) // 2:]
  return ys, zs
  
def merge(l, r):
  match l, r:
    case _, []: return l 
    case [], _: return r 
    case [x, *xs], [y, *ys]:
      if x <= y:
        return [x, *merge(xs, r)]
      return [y, *merge(l, ys)]

print(merge([2,4,6], [1,3,5]))
print(msort([5,1,4,3,2]))
print(halve([1,2,3]))