Merge Sort

Algorithm: Merge-Sort (numbers[], p, r) 
	if p < r then  
	    q = ⌊(p + r) / 2⌋ 
	    Merge-Sort (numbers[], p, q) 
	    Merge-Sort (numbers[], q + 1, r) 
	    return Merge (numbers[], p, q, r)   

Function: Merge (numbers[], p, q, r)
	n1 = q – p + 1 
	n2 = r – q 
	declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
	for i = 1 to n1 
	   leftnums[i] = numbers[p + i - 1] 
	for j = 1 to n2 
	   rightnums[j] = numbers[q+ j] 
	leftnums[n1 + 1] = ∞ 
	rightnums[n2 + 1] = ∞ 
	i = 1 
	j = 1 
	for k = p to r 
	   if leftnums[i] ≤ rightnums[j] 
		  numbers[k] = leftnums[i] 
		  i = i + 1 
	   else
		  numbers[k] = rightnums[j] 
		  j = j + 1 

DAA - Merge Sort

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result
print (MergeSort([1, 2, 30, 4, 5, 6, 7, 90, 21, 23, 45]))