why does python takes longer time to sort a copy of list?
<p>Why is there so much difference when sorting x and y and y is just a copy of x? Does python not copy the list right away?    </p>

<pre><code>python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); x.sort()'
100000 loops, best of 3: 19.5 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); y.sort()'
1000 loops, best of 3: 211 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'x.sort()'
100000 loops, best of 3: 15.9 usec per loop
</code></pre>

<p>Your first and last examples have to sort the list <strong>just once</strong>. After that, the sorting algorithm Python uses has an easy time of it as it is optimised to take advantage of <em>already sorted sequences</em>.</p>

<p>From the <a href="https://en.wikipedia.org/wiki/Timsort" rel="nofollow">Wikipedia article on TimSort</a> (the Python sorting algorithm):</p>

<blockquote>
  <p>The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.</p>
</blockquote>

<p>In other words, the <code>list(y); y.sort()</code> case is <em>disadvantaged</em> because it is given a clean, unsorted list each time. The <code>x.sort()</code> case is  given a fully sorted list (after the first iteration). After all, <code>list.sort()</code> sorts <em>in place</em>, altering the list. The <code>timeit</code> test does not create a copy for each test, so subsequent tests re-use the same list.</p>

<p>If you switch to using the <code>sorted()</code> function, you'll see no time advantage anymore, as <code>sorted()</code> returns a <em>new, copied and sorted list</em> instead of sorting in-place:</p>

<pre><code>python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); sorted(x)'
10000 loops, best of 3: 151 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); sorted(y)'
10000 loops, best of 3: 155 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'sorted(x)'
10000 loops, best of 3: 152 usec per loop
</code></pre>

python performance sorting timeit