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

from random import randint
import time

z = 0
y = 0
x = 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,9999999)

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


# binarysearch liefert den Wert True, falls value als Inhalt einer Komponente
# des Arrays array vorkommt, andernfalls liefert binarysearch den Wert False.

def binarysearch(array,value):
     global z
     z += 1
     #print(array)
     if array == [] or (len(array) == 1 and array[0] !=  value):
         return False
     else:
         midvalue = array[len(array)//2]
         if midvalue == value:
             return True
         elif value < midvalue:
             return binarysearch(array[:len(array)//2],value)
         else:
             return binarysearch(array[len(array)//2 + 1:],value)
            

# merge mischt zwei sortierte Teillisten zu einer sortierten Liste

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 x
    x +=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()

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:  ',x)
print('# Aufrufe merge: ',y)
print()    
value = int(input('gesuchtes Element: '))
print()

# Aufruf der Funktion binarysearch zur Suche von value im Array a

start = time.time()

result = binarysearch(a,value)

end = time.time()


if result == True: 
    print(value,'wurde gefunden')
else:
    print(value,'wurde nicht gefunden')

print()
print('Zeitaufwand BinarySearch bei',n,'Elementen: {:7.3f} s'.format(end-start))
print('# Aufrufe binarysearch: ',z)