## 10-3c) Take n numbers from x to y  n=1000 x=1 y=1000000 as given and implement Insertion sorting.
##    Implement the improvement of binary search while searching within the subset of sorted elements.

from time import clock
import sys

## Start
def Binary_Search (num_list,low,high,key):
    if (low==high):
        return low
    mid = low + ((high-low)/2)
    if key > num_list[mid]:
        return Binary_Search (num_list,mid + 1,high,key)
    elif (key < num_list[mid]):
        return Binary_Search(num_list,low,mid,key)
    return mid

def Binary_Insertion_Sort(Unsorted_List):
    length=len(Unsorted_List)
    memory=0
    for i in range (1,length,1):
        ins=Binary_Search(Unsorted_List,0,i,Unsorted_List[i])
        if ins<i:
            temp=Unsorted_List[i]
            for j in range (i-1,ins+1,-1):
                Unsorted_List[j+1]=Unsorted_List[j]
            Unsorted_List[ins]=temp
    memory=memory + sys.getsizeof(Unsorted_List) + sys.getsizeof(i)+ sys.getsizeof(ins)                
    return Unsorted_List,memory        


## End
temp=[]
data=[]

InFile=open("in10_3.txt",'r+')
for row in InFile:
    temp=row.split(',')
    for i in temp:
        data.append(int(i))
InFile.close()
Start=clock()
Insertion_Sort,memory_used=Binary_Insertion_Sort(data)
Time_Taken=clock()-Start

OutFile=open("out_r3_10_3c.txt","w")
OutFile.write("\n Sorted List Is as Follows :-  \n" )
OutFile.write(str(Insertion_Sort))
OutFile.write("\n\n Time Taken = " + str(Time_Taken) + " Seconds. ")
OutFile.write("\n Memory  Used = " + str(memory_used) + " Bytes. ")
OutFile.close()