Why is the execution time for my sorting code inconsistent?
<p>I'm learning python and I've implemented a quicksort algorithm (kind of). I do know that python's <code>sort()</code> method would be faster but I wanted to know by how much, so I've used the <code>timeit</code> module for comparison.</p>

<p>I created a 'wrapper' function for the <code>sort()</code> method so it works with the same syntax as my implementation (and stops being an in-place sort) and called <code>timeit.repeat(3, 2000)</code> for both functions.</p>

<p>Here are the results for my function:</p>

<pre><code>[0.00019502639770507812, 0.00037097930908203125, 0.00013303756713867188]
</code></pre>

<p>And for python's sort():</p>

<pre><code>[0.0001671314239501953, 0.0001678466796875, 0.00016808509826660156]
</code></pre>

<p>As you can see, python's algorithm has execution times much more consistent than my own's. Does anyone know why?</p>

<p><strong>Code:</strong></p>

<pre><code>import timeit
import random


def quick(lst):
    if not lst:
        return []
    else:
        first, rest = lst[0], lst[1:]
        great = []
        less = []
        for item in rest:
            great.append(item) if item &gt;= first else less.append(item)
        return quick(less) + [first] + quick(great)

def sort(lst):
    lst.sort()
    return lst


x = [random.randint(1, 10000) for i in xrange(1, 1000)]

quick_t = timeit.Timer("'quick(x)'")

print quick_t.repeat(3, 2000)

sort_t = timeit.Timer("'sort(x)'")

print sort_t.repeat(3, 2000)
</code></pre>

<p>Your timing is horribly wrong in multiple ways. First, your <code>sort</code> wrapper still mutates its input instead of returning a new list:</p>

<pre><code>&gt;&gt;&gt; x = [2, 1]
&gt;&gt;&gt; sort(x)
[1, 2]
&gt;&gt;&gt; x
[1, 2]
</code></pre>

<p>Second, you're not timing either sort at all. You're timing the evaluation of the string literal <code>'quick(x)'</code> or <code>'sort(x)'</code>. No sorting actually takes place.</p>

<p>Here's how you'd <em>actually</em> perform the timing:</p>

<pre><code>&gt;&gt;&gt; x = [random.randint(1, 10000) for i in xrange(1, 1000)]

&gt;&gt;&gt; print timeit.repeat('quick(x)', 'from __main__ import quick, x', repeat=3, number=500)
[1.1500223235169074, 1.0714474915748724, 1.0657452245240506]
&gt;&gt;&gt; print timeit.repeat('sorted(x)', 'from __main__ import quick, x', repeat=3, number=500)
[0.0944752552401269, 0.10085532031979483, 0.09799135718691332]
</code></pre>

python performance sorting time