title: Huge difference in timing between sorting a set vs sorting a list in Python
body: <p>I was wondering whether I should have my data structure as a set or a list. Mostly I will do set operations, but in the end I will need to sort it. </p>
  
  <p>I wondered whether I should first make the set a list, and then use <code>sorted(list(my_set))</code>, or just sort the set immediately <code>sorted(my_set)</code>. Arguably, I might consider a general "to list" phase, since having an ordered iterable at that point in time might make sense anyway.</p>
  
  <p>So I decided to test it, expecting a list to be quicker.</p>
  
  <p>Benchmarker: </p>
  
  <pre><code>import time
  def sorter(x):
      t1 = time.time()
      for i in range(1000000):
          sorted(x)
      return time.time() - t1
  </code></pre>
  
  <p>Data:</p>
  
  <pre><code>one = range(1000)
  a1 = list(one)
  b1 = set(one)
  sorter(a1)
  # time: 16.5 s 
  sorter(b1)
  # time: 20.7 s
  </code></pre>
  
  <p>I then realized it might have to do with the fact that the elements are already in place, and remembered <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array/11227902#11227902">this amazing question &amp; answer</a>.</p>
  
  <p>Then, I tried some random data:</p>
  
  <pre><code>two = numpy.random.randint(1, 1000, 1000)
  a2 = list(two)
  b2 = set(two)
  </code></pre>
  
  <p>With the results:</p>
  
  <pre><code>sorter(a2)
  # time: 4min 49s
  sorter(b2)
  # time: 18.9 s
  </code></pre>
  
  <p>Huge difference, what is going on?</p>
  
  <p>Bonus: It even appears at a timing of one minute, that <code>sorted(set(a_list))</code> is impressively faster than <code>sorted(a_list)</code>. </p>
  
  <p>Indeed in the second case, there can be duplicates which would be filtered, and thus speed up sorting.</p>