Why is there a huge difference in performance though time complexity for the two functions below seems to be similar?

Question

I am trying to evaluate the performance of two Python methods that sort a list of numbers. The time complexity seems to be n^2 for both of them but empirical data shows one performs better than the other. Any reasons for this?

I wrote two methods, one using nested for loops and another that finds a max and adds the max to a new list (and removes from the old list) iteratively.

Method 1:

def mysort1(l):
    i = 0
    j = 1
    for i in range(0,len(l)-1):
        for j in range(i,len(l)):
            if l[i] > l[j]:
                tmp = l[j]
                l[j] = l[i]
                l[i] = tmp
    return l

Method 2:

def mysort2(l):
    nl = []
    for i in range(0,len(l)):
        m = max(l)
        nl.insert(0, m)
        l.remove(m)
    return nl

Both were tested with a list of 10000 numbers in reverse order. When using profile, Method 1 takes approximately 8 seconds (10000+ calls) and method 2 takes only 0.6 seconds (30000+ calls). Any reason why Method 2 performs so much better than Method 1 even though time complexity for both seems to be the same?

Answer 1

Essentially, as the comments have suggested, it boils down to the major implementation of Python in C. This answer points out that the real reason is that the C counterpart, the native implementation of the list operations max etc, is much faster than your Python implementation due to many people optimizing the code and generally, C runs faster than Python for operations like this.

Here is another answer to the question "Why are Python Programs often slower than the Equivalent Program Written in C or C++?".

From the answer:

Internally the reason that Python code executes more slowly is because code is interpreted at runtime instead of being compiled to native code at compile time.

Other interpreted languages such as Java bytecode and .NET bytecode run faster than Python because the standard distributions include a JIT compiler that compiles bytecode to native code at runtime. The reason why CPython doesn't have a JIT compiler already is because the dynamic nature of Python makes it difficult to write one. There is work in progress to write a faster Python runtime so you should expect the performance gap to be reduced in the future, but it will probably be a while before the standard Python distribution includes a powerful JIT compiler.