import sys

'''
This is a simple function to find median of array of
five elements

It takes 7 comparisons
'''


def median_small(arr, left, right):
    arr[left:right]=sorted(arr[left:right])
    return arr[(left+right)//2]

# Partition subprocedure

def partition(arr, left, right, x):
    ind=left
    j=left
    while ind<right:
        if(arr[ind]==x):
            break
        ind=ind+1
    arr[ind], arr[right]=arr[right], arr[ind]

    pivot_pos=left
    j=left
    while (j<right):
        if (arr[j]<=x):
            arr[pivot_pos], arr[j]=arr[j], arr[pivot_pos]
            pivot_pos=pivot_pos+1
        j=j+1
    arr[pivot_pos], arr[right]=arr[right], arr[pivot_pos]
    return pivot_pos

# Median of medians of 5 elements, worst case time complexity : O(n)

def nth_order(arr, left, right, k):

    n=right-left+1
    if (k>0 and k<=n):

        n_by_five=n//5
        i=0
        i_five=0
        med_array=[0]*((n+4)//5)
        while (i<n_by_five):
            med_array[i]=median_small(arr, left+i_five, left+i_five+5)
            i_five=i_five+5
            i=i+1
        if(i_five<n):
            med_array[i]=median_small(arr, left+i_five, left+i_five+(n%5))
            i=i+1
            i_five=i_five+5

        pivot_element=med_array[0]
        if i>1:
            pivot_element=nth_order(med_array, 0, i-1, i//2)

        pivot_pos=partition(arr, left, right, pivot_element)

        if((pivot_pos-left)==(k-1)):
            return arr[pivot_pos]
        elif ((pivot_pos-left)>(k-1)):
            return nth_order(arr, left, pivot_pos-1, k)
        else:
            return nth_order(arr, pivot_pos+1, right, k-pivot_pos+left-1)

    else:
        return sys.maxsize

def median(arr):

    n=len(arr)
    mid=n//2+1

    if n==0:
        raise StatisticsError("no median for empty data")

    elif (n%2)==1:
        return nth_order(arr, 0, n-1, mid)

    else:

        med_high=nth_order(arr, 0, n-1, mid)
        #print (med_high)
        '''
        Now, we know that all elements less than 'mid_high' are in range of 0...mid-1.
        Therefore, the med_low will be largest element in range of 0...mid-2
        Which takes n/2-1 comparisons to find the max element
        '''
        med_low=max(arr[0:mid-1])
        return (med_low+med_high)/2.0

if __name__=="__main__":

    testarray=[]

    if len(sys.argv)==1:
        testarray=[233,32,3,322,45]
        print (findmedian(testarray))
        print (testarray)

    elif len(sys.argv)==2:
        import random
        testarray=[0]*int(sys.argv[1])
        for i in range(len(testarray)):
            testarray[i]=random.randint(0,1000)
        print (findmedian(testarray))
        print (testarray)

    else:
        print ("Invalid arguments")