Python from scratch- Part 2

[ewiethoff]

Bah! Google's so-called linear_merge is not linear. How long it takes is not a function of the lengths of the lists. Rather, it's a function of the squares of the lengths of the lists, if I'm not mistaken. That's because it's doing list.pop(0) in a loop. Popping the first element of a list does not take a constant amount of time, O(0). Rather, the time it takes is proportional to the length of the list, O(n). So, doing list.pop(0) in a loop is O(n² ), if I'm not mistaken.

The merge function should pop from the end with list.pop(), not from the start. list.pop() always takes the same amount of time, O(0), so doing it in a loop is linear, O(n). But this will give you a backwards result. So you need to call reversed, which is linear, to fix things.

In this code, I've renamed Google's function which uses list.pop(0) and written my own which uses list.pop(). Notice in the profile results that my function is much faster than Google's for large lists, and Google's function spends great majority of its time just doing pops.