Sorting

Merge Sort

The best way to conceptualize the merge sort is through recursion. It is based on divide and conquer.

def merge(A,B):
	p1=0
	p2=0
	result=[]
	while(p1<len(A) and p2<len(B)):
		if(A[p1] <B[p2]):
			result.append(A[p1])
			p1+=1
		else:
			result.append(B[p2])
			p2+=1
	if(p1==len(A)):
		result.extend(B[p2:])
	else:
		result.extend(A[p1:])

	return result


def merge_sort(A):
	if(len(A)<=1):
		return A

	left,right=merge_sort(A[:int(len(A)/2)])merge_sort(A[int(len(A)/2):]) 
	
	
	return merge(left,right)



print(merge_sort([-90,2,-23,-56,24,2,1,5]))