# MergeSort
# Aufwand = O(n*log(n))

from random import randint
import time

z = 0
y = 0

n = int(input('Laenge des arrays: '))
print()

# Erzeugen des arrays mit dem Namen a 
# und den n Komponenten a[0], . . . , a[n-1]
a = list(range(1,n+1))

# Zuweisung von Zufallszahlen an die Komponenten des arrays a
for i in range(0,n):
    a[i] = randint(0,999999)

# Ausgabe der Quelliste
r = int(input('Wieviele Elemente sollen angezeigt werden? '))
print()
for i in range(0,r): print(a[i])


# merge mischt zwei sortierte Teillisten zu einer sortierten Liste
# https://www.javatpoint.com/merge-sort-in-python

def merge(array, left, middle, right):  
 
    global y
    y += 1
    
    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] <= right_sublist[right_sublist_index]:  
            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):  
    global z
    z +=1
    if left == right: return  
    middle = (left + right)//2  
    sort(array, left, middle)  
    sort(array, middle + 1, right)  
    merge(array, left, middle, right)
  
 
  
start = time.time()

# Aufruf zum Sortieren der Liste a
sort(a, 0, len(a)-1)  

end = time.time()


print()
print('Sortierte Liste:')
print()
for i in range(0,r):
    print(a[i])


print()
print('Zeitaufwand zum Sortieren von',n,'Elementen: {:7.3f} s'.format(end-start))
print('# Aufrufe sort:  ',z)
print('# Aufrufe merge: ',y)