Skip to content

Instantly share code, notes, and snippets.

@bkrmalick
Created December 2, 2018 21:17
Show Gist options
  • Save bkrmalick/71b90c8db5ddb89aa8485888c1c23e67 to your computer and use it in GitHub Desktop.
Save bkrmalick/71b90c8db5ddb89aa8485888c1c23e67 to your computer and use it in GitHub Desktop.
Iterative Merge Sort in Python
def merge(A,B):
ca=0
cb=0
C=[]
for i in range(0,len(A)+len(B)):
if(ca>=len(A)):
x=B[cb]
cb+=1
elif(cb>=len(B)):
x=A[ca]
ca+=1
else:
if(A[ca]<B[cb]):
x=A[ca]
ca+=1
else:
x=B[cb]
cb+=1
C.append(x)
return C
def mergeSort(A):
if(len(A)>1):
sz=1
while(sz<len(A)):
i=0
while(i<len(A)):
C=[]
r=A[i:i+sz]
l=A[i+sz:i+sz+sz]
C=merge(r,l)
for k in range(i,i+len(C)):
A[k]=C[k-i]
i=i+sz
sz=sz*2
A=[1,3,23,5,6,8]
mergeSort(A)
for i in A:
print(i, end=',')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment