# MergeSort
# complexity: O(n*log(n))
# to be sorted: an array of n random integers taken from [1, 1E6] 


def MergeSort(array, lower, upper):

    if lower >= upper:
        return

    middle = (lower + upper)//2  # integer division
    MergeSort(array, lower, middle)
    MergeSort(array, middle + 1, upper)
    merge(array, lower, upper, middle)


def merge(array, lower, upper, middle):
    # make copies of both arrays to be merged
    # the second parameter is non-inclusive, therefore: increase by 1
    left_copy = array[lower : middle + 1]
    right_copy = array[middle + 1 : upper + 1]
    left_copy_index = 0
    right_copy_index = 0
    sorted_index = lower

    while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):
        if left_copy[left_copy_index] <= right_copy[right_copy_index]:
            array[sorted_index] = left_copy[left_copy_index]
            left_copy_index = left_copy_index + 1
        else:
            array[sorted_index] = right_copy[right_copy_index]
            right_copy_index = right_copy_index + 1
        sorted_index = sorted_index + 1

    while left_copy_index < len(left_copy):
        array[sorted_index] = left_copy[left_copy_index]
        left_copy_index = left_copy_index + 1
        sorted_index = sorted_index + 1

    while right_copy_index < len(right_copy):
        array[sorted_index] = right_copy[right_copy_index]
        right_copy_index = right_copy_index + 1
        sorted_index = sorted_index + 1


import time
from random import randint

print ('Anzahl der Datenelemente (Zuallszahlen aus [1,..,1000000]):')
n=int(input("n = "))
print ('Wieviele Datenelemente sollen jeweils angezeigt werden?')
max=int(input("max = "))
max=max+1
print()
print('zu sortierende Liste:')

n = n + 1
array = list(range(1, n+1))

for i in range (1, n):
    array[i]=randint(1, 1000000)
if max <= n:
    for i in range (1, max):   
        print(array[i])
print()
print('sortierte Liste:')


start = time.time()

MergeSort(array, 0, len(array) - 1)

end = time.time()


if max <= n:
    for i in range (1, max):   
        print(array[i])
        

print()
print('Zeitaufwand MergeSort: {:5.3f} s'.format(end-start),'bei', n-1,'Datenelementen')