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

from random import randint
import time

z = 0 # z = Anzahl Aufrufe sort
y = 0 # y = Anzahl Aufrufe merge 
x = 0 # x = Anzahl Aufrufe binarysearch

n = int(input('Laenge n 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(n): a[i] = randint(0,999999)

# Ausgabe der Quelliste
condition = True
while condition:
   r = int(input('Wieviele Elemente sollen angezeigt werden (hoechstens 100)? '))
   if r <= 100: condition = False
print()
print('Die ersten',r,'Datenelemente der Quelliste:')
print(a[:r])

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)

def binarysearch(value, array, begin, end):
    global x
    x += 1
    if begin > end: return -1
    middle = (begin + end) // 2
    if   value == array[middle]: return middle
    elif value <  array[middle]: return binarysearch(value, array, begin, middle - 1)
    else:                        return binarysearch(value, array, middle + 1, end)
    
   
start = time.time()

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

end   = time.time()

MergeSortTime = end - start

print()
print('Die ersten',r,'Datenelemente der sortierte Liste:')
print(a[:r])

print()
value = int(input('gesuchtes Datenelement: '))
print()

start = time.time()

index = binarysearch(value, a, 0, len(a) - 1)

end   = time.time()

BinarySearchTime = end - start

if index == -1: print(value,' nicht gefunden')
else: print('gefunden: a[',index,'] =', a[index])

print()
print('Zeitaufwand zum Sortieren von',n,'Elementen: {:7.3f} s'.format(MergeSortTime))
print('Zeitaufwand zur Suche in',n,'Elementen: {:12.3f} s'.format(BinarySearchTime))
print('# Aufrufe sort: {0:10}'.format(z))
print('# Aufrufe merge:{0:10}'.format(y))
print('# Aufrufe binarysearch:{0:3}'.format(x))

print()
dummy = 1
while dummy == 1: dummy = input('press ENTER to leave ')