Archives

You should also probably modify insort so…

Comment on “BList” by Daniel Stutzbach

You should also probably modify insort so that it uses the b-tree structure to still run in log(n) instead of log(n) ** 2, which it will do if it has to treat the underlying blist as a black box.

It makes use of the BList structure, so it's worst-case O(log(n)) now (see left figure). The regular list does some extra tricks to get O(n) performance on mostly-sorted data, which I have not attempted to reproduce yet.

Share

Comments are closed.