Part 1: Merge

Merge two list into one by order

def merge(l1,l2):
	if not (len(l1) and len(l2)):
		return l1+l2
	else:
		if l1[0]<l2[0]:
			return [l1[0]]+merge(l1[1:],l2[:])
		else:
			return [l2[0]]+merge(l1[:],l2[1:])

Part 2: Sort

def sort(l):
	if len(l)<2:
		return l
	else:
		return merge(sort(l[:len(l)//2]),sort(l[len(l)//2:]))

def sort(l):
	if l:
		return merge([l[0]],sort(l[1:]))
	else:
		return []

def sort(l):
	if len(l)<2:
		return l
	else:
		return merge(sort(l[::2]),sort(l[1::2]))

Let us see the result.

Test code:

from random import shuffle as r

def merge(l1,l2):
	if not (len(l1) and len(l2)):
		return l1+l2
	else:
		if l1[0]<l2[0]:
			return [l1[0]]+merge(l1[1:],l2[:])
		else:
			return [l2[0]]+merge(l1[:],l2[1:])

def sort(l):
	if len(l)<2:
		return l
	else:
		return merge(sort(l[:len(l)//2]),sort(l[len(l)//2:]))

_=list(range(1,101))
r(_)
print(_)
print(sort(_))

• Result