title: Python quicksort - List comprehension vs Recursion (partition routine)
body: <p>I watched the talk Three Beautiful Quicksorts and was messing around with quicksort. My implementation in python was very similar to c (select pivot, partition around it and recursing over smaller and larger partitions). Which I thought wasn't <em>pythonic</em>. </p>
  
  <p>So this is the implementation using list comprehension in python. </p>
  
  <pre><code>def qsort(list):
      if list == []: 
          return []
      pivot = list[0]
      l = qsort([x for x in list[1:] if x &lt; pivot])
      u = qsort([x for x in list[1:] if x &gt;= pivot])
      return l + [pivot] + u
  </code></pre>
  
  <p>Lets call the recursion metho qsortR. now I noticed that qsortR runs much slower than qsort for large(r) lists. Actually "maximum recursion depth exceeded in cmp" even for 1000 elems for recursion method. Which I reset in sys.setrecursionlimit.</p>
  
  <p>Some numbers:</p>
  
  <pre><code>list-compr 1000 elems 0.491770029068
  recursion 1000 elems 2.24620914459
  list-compr 2000 elems 0.992327928543
  recursion 2000 elems 7.72630095482
  </code></pre>
  
  <p>All the code is <a href="https://gist.github.com/3448918" rel="noreferrer">here</a>.</p>
  
  <p>I have a couple of questions:</p>
  
  <ul>
  <li>Why is list comprehension so much faster?</li>
  <li>Some enlightenment on the limit on recursion in python. I first set it to 100000 in what cases should I be careful? 
  
  <ul>
  <li>(What exactly is meant by 'optimizing tail recursion', how is it done?)</li>
  </ul></li>
  <li>Trying to sort 1000000 elements hogged memory of my laptop (with the recursion method). What should I do if I want to sort so many elements? What kind of optimizations are possible?</li>
  </ul>