import sys
import time
class merge:
    
    def __init__(self,lst1):
        self.lst=lst1
        
    def divide(self,mi,ma):
        x=ma-mi
        if(x <= 1):
            if(self.lst[ma]<self.lst[mi]):
                temp=self.lst[mi]
                self.lst[mi]=self.lst[ma]
                self.lst[ma]=temp
            return
        
        z=mi+((ma-mi)/2)
        self.divide(mi,z)
        self.divide(z+1,ma)
        self.merg(mi,z,ma)
        
     
            
    def merg(self,mi,mid,ma):
        global swap
        global comp
        i=mi
        j=mid+1
        while j <= ma and i<= mid :
            if(self.lst[i]>self.lst[j]):
                comp=comp+1
                swap=swap+1
                temp=self.lst[j]
                k=j
                while k!=i:
                    self.lst[k]=self.lst[k-1]
                    k=k-1
                self.lst[i]=temp
                j=j+1
                i=i+1
                mid=mid+1

            else:
                i=i+1
                
    def display(self) :
        f2.write(str(self.lst))
swap=0
comp=0
f1=open('in_10_5.txt','r')
z=f1.readline()
a1=z.split(", ")
z1=f1.readline()
a2=z1.split(", ")
z2=f1.readline()
a3=z2.split(", ")
z3=f1.readline()
a4=z3.split(", ")
z4=f1.readline()
a5=z4.split(", ")
for i in range(0,len(a1)):
    a1[i]=int(a1[i])
for i in range(0,len(a2)):
    a2[i]=int(a1[i])    
for i in range(0,len(a3)):
    a3[i]=int(a1[i])
for i in range(0,len(a4)):
    a4[i]=int(a1[i])
for i in range(0,len(a5)):
    a5[i]=int(a1[i])    
t1=time.clock()
f2=open('out_25_10_5_3.txt','w')
f2.write('Set 1:\n')
dd=merge(a1)
dd.divide(0,(len(a1)-1))
dd.display()
f2.write('\nSet 2:\n')
dd.display()
f2.write('\nSet 3:\n')
dd.display()
f2.write('\nSet 4:\n')
dd.display()
f2.write('\nSet 5:\n')
dd.display()
f1.close()
t2=time.clock()
t=t2-t1
mem=sys.getsizeof(a1)+sys.getsizeof(a2)+sys.getsizeof(a3)+sys.getsizeof(a4)+sys.getsizeof(a5)
f2.write("\nNo. of Swaps=%d\nNo.of Comparisons=%d\n"%(swap,comp))
f2.write("Time Taken=%f\nmemory used=%d bytes"%(t,mem))
f2.close()