#The Merge Function Using POP

def merge(list1,list2):
    newlist = []
    while list1 and list2:
        if list1[0] < list2[0]:
            newlist.append(list1.pop(0))
        else:
            newlist.append(list2.pop(0))

    #Appending Final Items So Either List Not Empty
    while list1:
        newlist.append(list1.pop(0))
    while list2:
        newlist.append(list2.pop(0))
    return newlist

#The Merge Function With Markers

##def merge(list1,list2):
##    newlist = []
##    amark = 0
##    bmark = 0
##    while amark < len(list1) and bmark < len(list2):
##        if list1[amark] < list2[bmark]:
##            newlist.append(list1[amark])
##            amark = amark + 1
##        else:
##            newlist.append(list2[bmark])
##            bmark = bmark + 1
##
##    #Appending Final Items So Either List Not Empty
##    for i in range(amark, len(list1)):
##        newlist.append(list1[i])
##    for i in range(bmark, len(list2)):
##        newlist.append(list2[i])
##    return newlist

#The Sorting Part:

def sort(array):

    if len(array) == 1:
        return array

    mid = len(array) // 2
    left = array[:mid]
    right = array [mid:]

    left = sort(left)
    right = sort(right)

    return merge(left,right)


file = open("townlist.txt","r")
townlist = []
for line in file:
    town = line.strip()
    town = town.lower()
    townlist.append(town)


midpoint = len(townlist) // 2
list1 = townlist[:midpoint]
list2 = townlist[midpoint:]

mergefunction = merge(list1, list2)
sortingpart = sort(mergefunction)

print(sortingpart)