search instagram arrow-down

Archives

Categories

Meta

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]))
Leave a Reply
Your email address will not be published. Required fields are marked *

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: