Test performance of python's bisect and best data struture to work with it

bisect_sort.py

import timeit

setup='''
import random, bisect
from collections import deque

random.seed('slartibartfast')
s = [random.random() for i in range(1000)]
timsort = sorted

def bisect_list(seq):
    for i in range(1, len(seq)):
        bisect.insort(seq, seq.pop(i), 0, i)
        
def bisect_deque(seq):
    ans = deque([])
    for x in seq:
        pos = bisect.bisect_left(ans, x)
        ans.insert(pos, x)
    return ans
'''
# run 1000 times, repeat 7 times, get the best
print("Timsort-List {}".format(min(timeit.Timer('a=s[:]; timsort(a)', setup=setup).repeat(7, 1000)))) # 0.117
print("Timsort-Deque {}".format(min(timeit.Timer('a=deque(s[:]); timsort(a)', setup=setup).repeat(7, 1000)))) # 0.124
print("Bisect-List {}".format(min(timeit.Timer('a=s[:]; bisect_list(a)', setup=setup).repeat(7, 1000)))) # 0.64109
print("Bisect-Deque {}".format(min(timeit.Timer('a=deque(s[:]); bisect_deque(a)', setup=setup).repeat(7, 1000)))) # 0.63