gistfile1.txt

import numpy.random as random
from time import clock

def r_step_generator(lo, hi):
    num = lo
    diff = hi - lo
    while True:
        num += random.randint(0, diff)
        if num < hi:
            yield num
        else:
            raise StopIteration
  	    
N=100000000
t1=clock()
u=range(0,N)
x=random.randint(0,N,N/100)
y=0
for i in r_step_generator(0,N):
    if i>len(u):
        break
    u.insert(x[y],i)
    y+=1
t2=clock()
print t2-t1