@@ -0,0 +1,1721 @@
+from random import shuffle%0A%0Adef hoare ( compare , a , i , j ) :%0A%0A    o = i%0A    x = a%5Bo%5D%0A%0A    while True :%0A%0A        while True :%0A%0A            j -= 1%0A%0A            if i %3E= j :%0A%0A                a%5Bo%5D = a%5Bj%5D%0A                a%5Bj%5D = x%0A                return j%0A%0A            elif compare( x , a%5Bj%5D ) %3E 0 : break%0A%0A        while True :%0A%0A            i += 1%0A%0A            if i %3E= j :%0A%0A                a%5Bo%5D = a%5Bj%5D%0A                a%5Bj%5D = x%0A                return j%0A%0A            elif compare( x , a%5Bi%5D ) %3C 0 : break%0A%0A        # invariant i %3C j%0A%0A        t    = a%5Bi%5D%0A        a%5Bi%5D = a%5Bj%5D%0A        a%5Bj%5D =    t%0A%0A%0Adef quickselect ( compare , k , a , i, j ) :%0A%0A    if j - i %3C 2 : return%0A    %0A    pivot = hoare( compare , a , i , j )%0A%0A    if k == pivot  : return%0A    elif k %3C pivot : quickselect( compare , k , a ,         i , pivot )%0A    else           : quickselect( compare , k , a , pivot + 1 ,     j )%0A%0A%0Adef asc ( a , b ) :%0A%0A    return -1 if a %3C b else 0 if a == b else 1%0A%0A%0Adef checkio(data):%0A%0A    shuffle( data ) # otherwise sorted array would produce worst case%0A%0A    n = len( data )%0A%0A    k = n // 2%0A%0A    quickselect( asc , k , data , 0 , n )%0A%0A    median = data%5Bk%5D%0A%0A    if not n & 1 : median = ( median + max( data%5B:k%5D ) ) / 2%0A%0A    return median%0A%0A%0A#These %22asserts%22 using only for self-checking and not necessary for auto-testing%0A%0Aif __name__ == '__main__':%0A%0A    assert checkio(%5B1, 2, 3, 4, 5%5D) == 3, %22Sorted list%22%0A    assert checkio(%5B3, 1, 2, 5, 3%5D) == 3, %22Not sorted list%22%0A    assert checkio(%5B1, 300, 2, 200, 1%5D) == 2, %22It's not an average%22%0A    assert checkio(%5B3, 6, 20, 99, 10, 15%5D) == 12.5, %22Even length%22%0A    print(%22Start the long test%22)%0A    assert checkio(list(range(1000000))) == 499999.5, %22Long.%22%0A    print(%22The local tests are done.%22)%0A%0A

Create median.py