# -*- coding: utf-8 -*-
"""
Created on Mon Apr  9 13:37:48 2018

@author: Agung Alfiansyah
"""
from random import randint
"""
def binarySearch(Lin, key):
    print(Lin)
    if len(Lin) == 0:
        return -1
    else:
        c = len(Lin)//2
        if Lin[c]==key:
            return c
        else:
            if key<Lin[c]:
                print(c," KIRI")
                return binarySearch(Lin[:c],key)
            else:
                print(c," KANAN")
                return binarySearch(Lin[c+1:],key)
"""

def binarySearch(Lin,l,r,key):
    if l==r-1:
        return -1
    else:
        c=(l+r)//2
        if Lin[c]==key:
            return c
        else:
            if key<Lin[c]:
                return binarySearch(Lin,l,c,key)
            else:
                return binarySearch(Lin,c,r,key)
"""
testlist = [i*2 for i in range(0,256)]
print(binarySearch(testlist,0,len(testlist),154))
"""

def binarySearchIterative(Lin,l,r,key):
    while l!=r-1:
        c=(l+r)//2
        print(l,c,r)
        if Lin[c]==key:
            return c
        elif Lin[c]>key:
            r=c
        else:
            l=c
    return -1

"""
testlist = [i*2 for i in range(0,256*256*256)]
print(binarySearchIterative(testlist,0,len(testlist),254*256))
"""

def LinearSearch(Lin,key):
    for i in range (0,len(Lin)):
        if Lin[i]==key:
            return i
    return -1

"""
testlist = [i*2 for i in range(0,256*2)]
print(LinearSearch(testlist,254*2-1))

"""

def Min(Lin):
    print(Lin)
    if len(Lin) == 1:
        #print(Lin[0])
        return Lin[0]
    elif len(Lin) == 2:
        if Lin[0]<=Lin[1]:
            #print(Lin[0])
            return Lin[0]
        else:
            #print(Lin[1])
            return Lin[1]
    else:
        c=len(Lin)//2
        L1=Min(Lin[:c])
        L2=Min(Lin[c:])
        return Min([L1,L2])

#testlist = [randint(0,256) for i in range(0,12)]
#print(Min(testlist))

def CountingSort(Lin,maxval):
    count=[0]*(maxval+1)

    for i in Lin:count[i]=count[i]+1
    Lsort=[]
    for i in range (0,maxval+1):
        for j in range (0,count[i]):
            Lsort.append(i)
    return Lsort



def partition(Lin, start, end):
    pivot = Lin[(start)]
    left = start+1
    right = end
    done = False
    print (left,right)
    while not done:
        while left <= right and Lin[left] <= pivot:
            left = left + 1
        while Lin[right] >= pivot and right >=left:
            right = right -1
        if right < left:
            done= True
        else:
            temp=Lin[left]
            Lin[left]=Lin[right]
            Lin[right]=temp
    # swap
    temp=Lin[start]
    Lin[start]=Lin[right]
    Lin[right]=temp
    return right

def QuickSort(Lin, start, end):
    if start < end:
        # partition the list
        pivot = partition(Lin, start, end)
        # sort both halves
        QuickSort(Lin, start, pivot-1)
        QuickSort(Lin, pivot+1, end)
    return Lin


#testlist = [randint(0,256) for i in range(0,16)]
#print(QuickSort(testlist,0,len(testlist)-1))



def merge(left, right):
    if not len(left) or not len(right):
        return left or right

    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j+= 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break
    return result

def MergeSort(list):
    if len(list) < 2:
        return list

    middle = len(list)//2
    left = MergeSort(list[:middle])
    right = MergeSort(list[middle:])

    return merge(left, right)

testlist = [randint(0,256*256) for i in range(0,16*256*256)]
print(MergeSort(testlist))