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

from random import randint
import time

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(1,1000000)

# Ausgabe des arrays
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 Gesamtliste
# https://www.javatpoint.com/merge-sort-in-python

def merge(array, left, middle, right):  
    
    # Creating subparts of arrays  
    left_sublist = array[left:middle + 1]  
    right_sublist = array[middle+1:right+1]  
  
    # Initial values for variables that we use to keep  
    # track of where we are in each array  
    left_sublist_index = 0  
    right_sublist_index = 0  
    sorted_index = left  
  
    # traverse both copies until we get run out one element  
    while left_sublist_index < len(left_sublist) and right_sublist_index < len(right_sublist):  
  
        # If our left_sublist has the smaller element, put it in the sorted  
        # part and then move forward in left_sublist (by increasing the pointer)  
        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  
        # Otherwise add it into the right sublist  
        else:  
            array[sorted_index] = right_sublist[right_sublist_index]  
            right_sublist_index = right_sublist_index + 1  
    
        # move forward in the sorted part  
        sorted_index = sorted_index + 1  
  
       
    # we will go through the remaining elements and add them  
    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)
  
 
  
start = time.time()

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))