import time
import time
import sys
class merge:
    def __init__(self,lst1):
        self.lst=lst1

    def divide(self,mi,ma):
        x=ma-mi
        if(x < 16):
            self.insertion(mi,ma)
            return
        
        z=mi+((ma-mi)/2)
        self.divide(mi,z)
        self.divide(z+1,ma)
        self.merg(mi,z,ma)

    def insertion(self,mi,ma):
        i=mi+1
        
        while i <=ma:
            x=self.lst[i]
            j=i-1
            while j>=mi:
                
                if self.lst[j]> x :
                    self.lst[j+1]=self.lst[j]
                    j=j-1
                else:
                    break
            
            self.lst[j+1]=x
            i=i+1
            
    def merg(self,mi,mid,ma):
        global comp
        a=[]
        i=mi
        j=mid+1
        while j <= ma and i<= mid :
            if(self.lst[i]>self.lst[j]):
                comp=comp+1
                a.append(self.lst[j])
                j=j+1
                
            else:
                a.append(self.lst[i])
                i=i+1
        
        while i<=mid :
            a.append(self.lst[i])
            i=i+1

        while j<=ma :
            a.append(self.lst[j])
            j=j+1
        i=mi
        j=0
        while i <= ma :
            self.lst[i]=a[j]
            i=i+1
            j=j+1
                
    def display(self) :
        f2.write(str(self.lst))
comp=0
f1=open('in_10_5.txt','r')
row1=f1.readline()
a1=row1.split(", ")
row2=f1.readline()
a2=row2.split(", ")
row3=f1.readline()
a3=row3.split(", ")
row4=f1.readline()
a4=row4.split(", ")
row5=f1.readline()
a5=row5.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_2.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 Comparisons=%d\n"%(comp))
f2.write("Time taken=%f\nMemory used=%dbytes"%(t,mem))
f2.close()