'''
Created on Nov 26, 2012

@author: ola
'''

import random,time,bisect,sys


def mergesort(values):

    def merge(low,mid,high):
        lindex = low
        rindex = mid+1
        temp = []
        while lindex <= mid and rindex <= high:
            if values[lindex] <= values[rindex]:
                temp.append(values[lindex])
                lindex += 1
            else:
                temp.append(values[rindex])
                rindex += 1
        temp.extend(values[lindex:mid+1])
        temp.extend(values[rindex:])
        index = low
        for val in temp:
            values[index] = val
            index += 1
            
    def dowork(low,high):
        if low < high:
            mid = (low+high)/2
            dowork(low,mid)
            dowork(mid+1,high)
            merge(low,mid,high)
    dowork(0,len(values)-1)

def qsort(values):
    def swap(a,b):
        values[a], values[b] = values[b],values[a]
        
    def partition(low,high):
        piv_value = values[low]
        piv = low
        for i in range(low+1,high+1):
            if values[i] < piv_value:
                piv += 1
                swap(piv,i)
        swap(piv,low)
        return piv 
                
    def dowork(low,high):
        if low < high:
            pivot = partition(low,high)
            dowork(low,pivot-1)
            dowork(pivot+1,high)
    
    dowork(0,len(values)-1)


def get_number():
    return random.randint(0,sys.maxint)

def create_list(n):
    return [get_number() for i in xrange(0,n)]

def binary_search(values,target):
    low = 0
    high = len(values)-1
    while low <= high:
        mid = (low+high)/2
        if values[mid] == target:
            return mid
        elif values[mid] < target:
            low = mid+1
        else:
            high = mid-1
    return -1

def linear_search(values,target):
    for i in range(len(values)):
        if values[i] == target:
            return i
    return -1


def make_lists(size,search_size):
    nums = create_list(size)
    search = create_list(search_size/2)
    search.extend(nums[:search_size/2])
    return nums,search

def timings(values,search_for, func):
    start = time.time()
    found = 0
    for x in search_for:
        ret = func(values,x)
        if ret != -1:
            found += 1
    end = time.time()
    print "%s:size = %d\tsearch = %d\tfound=%d\ttime = %4.3f" % (func,len(values), len(search_for),found,(end-start))

if __name__ == '__main__':
    LIST_SIZE = 10000
    for sval in range(1000,10001,1000):
        values,search = make_lists(LIST_SIZE,sval)
        qsort(values)
        timings(values,search,binary_search)