# MergeSort
# Eingabe: Vorname, Name
# Jeden aus Vorname und Name bestehenden Datensatz fassen wir
# als Liste mit zwei Komponenten auf.
# Die Komponenten des arrays a bestehen aus diesen Datensätzen.
# Das array a wird alphabetisch jeweils nach dem Namen, also nach
# der zweiten Komponente jedes Datensatzes, sortiert.

# Erzeugen des arrays [[' ' , ' ']]
a = [[' ' for j in range(2)] for i in range(1)]

condition = True
i = 0


def merge(array, left, middle, right):  
 
    left_sublist = array[left:middle + 1]  
    right_sublist = array[middle+1:right+1]  
     
    left_sublist_index = 0  
    right_sublist_index = 0  
    sorted_index = left  
  
    while left_sublist_index < len(left_sublist) and right_sublist_index < len(right_sublist):  
  
        if left_sublist[left_sublist_index][1] <= right_sublist[right_sublist_index][1]:  
            array[sorted_index] = left_sublist[left_sublist_index]  
            left_sublist_index = left_sublist_index + 1  
        else:  
            array[sorted_index] = right_sublist[right_sublist_index]  
            right_sublist_index = right_sublist_index + 1  
    
        sorted_index = sorted_index + 1  
   
    while left_sublist_index < len(left_sublist):  
        array[sorted_index] = left_sublist[left_sublist_index]  
        left_sublist_index = left_sublist_index + 1  
        sorted_index = sorted_index + 1  
  
    while right_sublist_index < len(right_sublist):  
        array[sorted_index] = right_sublist[right_sublist_index]  
        right_sublist_index = right_sublist_index + 1  
        sorted_index = sorted_index + 1 


def sort(array, left, right):  
    if left == right: return  
    middle = (left + right)//2  
    sort(array, left, middle)  
    sort(array, middle + 1, right)  
    merge(array, left, middle, right)

# Eingabe der zu sortierenden Datensätze
while condition:
    vorname = input('vorname: ')
    name = input('name:    ')
    if i == 0:
        a[i][0] = vorname
        a[i][1] = name
    else:
        a.append([vorname,name])
    ans = input('weiter? <y> <n> ')
    condition = ans == 'y'
    i +=1

print()
print('Quelliste:')
print(a)    
print()
for i in range(len(a)):
    print(a[i][0],' ',a[i][1])
print()

# Sortieren der Quelliste

sort(a, 0, len(a)-1) 

# Ausgabe der sortierten Liste

print('sortierte Liste:')
print(a)
print()

for i in range(len(a)):
    print(a[i][0],' ',a[i][1])