Inserir tudo não faz comparações, classificá-lo depois é em O (n * log (n)), então inserir e depois ordenar é em O (n * log (n))
Inserir um elemento em uma lista ordenada para manter uma lista ordenada é logarítmico no tamanho da lista, portanto, a inserção de n elementos nessa lista está em O (n * log (n)), já que o tamanho da lista cresce à medida que você continua inserindo elementos.
Portanto, ele tem uma complexidade semelhante em termos de comparações, mas inserir um elemento em python é muito mais caro do que acrescentar (linear com o tamanho da lista em vez de constante). O mais eficiente é, portanto, acrescentar tudo e depois ordenar.
Aqui está um exemplo de código para verificar o desempenho do processamento de números aleatórios de 10000:
import random
import timeit
import bisect
def append_then_sort(data):
result = []
for element in data:
result.append(element)
result.sort()
return result
def insert_sorted(data):
result = []
for element in data:
bisect.insort_left(result, element)
return result
if __name__ == '__main__':
numbers = [random.randint(0, 3000000) for _ in xrange(10000)]
print('Append then sort:')
print(timeit.timeit('append_then_sort(numbers)', setup='from __main__ import append_then_sort, numbers', number=10))
print('Insert sorted:')
print(timeit.timeit('insert_sorted(numbers)', setup='from __main__ import insert_sorted, numbers', number=10))
E os resultados na minha máquina:
Append then sort:
0.0509831905365
Insert sorted:
0.27309513092
Você também pode estar interessado em pesquisar no módulo sqlite3 que faz parte da biblioteca Python padrão por isso deve estar disponível em seu sistema. Eu não tenho certeza de como o sqlite lida com bancos de dados grandes, no entanto ...