import random

list10 = []
for x in range(10):
    list10.append(random.randrange(100))

list100 = []
for x in range(100):
    list100.append(random.randrange(100))

list1000 = []
for x in range(1000):
    list1000.append(random.randrange(100))

def sort_list(old_list):
    def find_new_index(old_i):
        for new_i in range(1, len(new_list)):
            if new_list[new_i] > old_list[old_i]:
                return new_i

    new_list = [old_list[0]]
    for old_i in range(1, len(old_list)):
        if old_list[old_i] <= new_list[0]:
            new_list.insert(0, old_list[old_i])
        elif old_list[old_i] >= new_list[len(new_list)-1]:
            new_list.insert(len(new_list), old_list[old_i])
        else:
            new_list.insert(find_new_index(old_i), old_list[old_i])
    return new_list

%time sort_list(list10)

%time sort_list(list100)

%time sort_list(list1000)

"""
Explanation: Implement the sorting algorithm you came up with in pseudocode with Python
Test the sorting algorithm with a list of 10, 100, 1000 random numbers and compare the result using the %time to time your code and submit your results in code comments
Input: a list of integer values
Operation: sort the list
Output: a sorted list of values
Note: Don't worry about checking data types, assume they'll always be integers but design for other error conditions
End of explanation
"""


def bsort_list(old_list):
    new_list = [old_list[0]]
    
    def find_new_index(old_i):
        start_index = 0
        end_index = len(new_list) - 1
        while end_index - start_index > 1:
            middle_index = int((end_index - start_index) / 2 + start_index)
            if old_list[old_i] == new_list[start_index]: 
                new_i = start_index
                return new_i
            elif old_list[old_i] == new_list[end_index]: 
                new_i = end_index
                return new_i
            elif old_list[old_i] == new_list[middle_index]:
                new_i = middle_index
                return new_i
            elif old_list[old_i] < new_list[middle_index]:
                end_index = middle_index
            else:
                start_index = middle_index
        new_i = end_index
        return new_i
    
    for old_i in range(1, len(old_list)):
        if old_list[old_i] < new_list[0]:
            new_list.insert(0, old_list[old_i])
        elif old_list[old_i] > new_list[len(new_list) - 1]:
            new_list.insert(len(new_list), old_list[old_i])  
        else:
            new_list.insert(find_new_index(old_i), old_list[old_i])
    return new_list

print(list10)
print(bsort_list(list10))

%time bsort_list(list10)

"""
Explanation: binary sorting
End of explanation
"""


%time bsort_list(list100)

"""
Explanation: sort_list(list10) was 29 µs, so this one is slower
End of explanation
"""


%time bsort_list(list1000)

"""
Explanation: sort_list() was total: 586 µs, so this one is slower
End of explanation
"""


