mergesort using imutability

mergesort.py

# using tail recursion

def merge(l, r, acc):
	if not l:
		return acc + r
	elif not r:
		return acc + l
	if l[0] < r[0]:
		return merge(l[1:], r, acc + [l[0]])
	else:
		return merge(l, r[1:], acc + [r[0]])

def msort(seq):
    mid = len(seq) / 2
    if mid == 0:
    	return seq
    else:
    	left = msort(seq[:mid])
    	right = msort(seq[mid:])
    	return merge(left, right, [])



# no tail recursion

def merge(l, r):
	if not l:
		return r
	elif not r:
		return l
	if l[0] < r[0]:
		return [l[0]] + merge(l[1:], r)
	else:
		return [r[0]] + merge(l, r[1:])

def msort(seq):
    mid = len(seq) / 2
    if mid == 0:
    	return seq
    else:
    	left = msort(seq[:mid])
    	right = msort(seq[mid:])
    	return merge(left, right)



print(msort([3, 1, 2, 0, 4, -1]))
# [-1, 0, 1, 2, 3, 4]