import sys
from time import clock
from array import array
       
def bucket_sort(data):
    global buckets
    buckets = [[] for x in range(100)] #list of empty buckets
    
    #place data into buckets
    
    for item in data:
        buckets[item /10000].append(item)
    
        
    #sort the buckets
    for bucket in buckets:
            insertion_sort(bucket)
           

    #sorted output           
    i = 0
    for bucket in buckets:
            for item in bucket:
                data[i] = item
                i += 1
 
def insertion_sort(data):
    i = 1
    global cmp
    cmp=0
    while i < len(data):
        cmp=cmp+1
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
                cmp=cmp+2
                data[j + 1] = data[j]
                j -= 1
        data[j + 1] = key
        i += 1

def main():
    start = clock()
    fin=open("in10_7.txt","r")
    fout=open("out_27_10_7.txt","w")
    a = array('i')
    global cmp
    global buckets
    k=0
    lc=0   
    for x in fin:
        if (lc%2!=0):
            a=[]
            for y in x.split(", "):
                y=y.strip(" ")
                a.append(int(y))
            bucket_sort(a)
                
            l=[]
            for i in range(0,len(a)):
                l.append(str(a[i]))
            
            fout.write("Sorted Set"+str(k+1)+":\n")
            fout.write(", ".join(l))
            fout.write("\n\n")
            k=k+1
        
        lc=lc+1
        
    end = clock()
    time= end - start
    fout.write("\n Total execuion time ="+ str(time)+ " seconds")
    m=sys.getsizeof(a)+sys.getsizeof(x)+sys.getsizeof(y)+sys.getsizeof(buckets)+sys.getsizeof(l)+sys.getsizeof(fin)+sys.getsizeof(fout)
    fout.write("\n Memory used= "+str(m)+" bytes")
    fout.write("\n Number of comparisons="+str(cmp))
            

    fin.close()
    fout.close()
main()