title: how to implement dual-pivot quicksort in Python
body: <p>So I've been trying to reproduce the dual-pivot Quicksort algorithm in Python 2.7; the basic one ran perfectly:</p>
  
  <pre><code>def quicksort_by_length(list, start, top):
      if top &lt;= start:
          return
      p = start
      k = start+1
      h = k
      while k &lt;= top:
          if list[k] &lt; list[p]:
              list[k], list[h] = list[h], list[k]
              h += 1
          k += 1
      h -= 1
      list[p], list[h] = list[h], list[p]
      quicksort_by_length(list, start, h-1)
      quicksort_by_length(list, h+1, top)
  </code></pre>
  
  <p>Next, I moved on to dual pivot and this was what I tried:</p>
  
  <pre><code>def dual_pivot_sort(list, start, top):
      if top &lt;= start:
          return
      p = start
      q = top
      k = p+1
      h = k
      l = q-1
      if list[p] &gt; list[q]:
          list[p], list[q] = list[q], list[p]
      while k &lt; top:
          if list[k] &lt; list[p]:
              list[h], list[k] = list[k], list[h]
              h += 1
          elif list[k] &gt; list[q]:
              list[k], list[l] = list[l], list[k]
              l -= 1
          k += 1
      h -= 1
      l += 1
      list[p], list[h] = list[h], list[p]
      list[q], list[l] = list[l], list[q]
      dual_pivot_sort(list, start, h-1)
      dual_pivot_sort(list, h+1, l-1)
      dual_pivot_sort(list, l+1, top)
  </code></pre>
  
  <p>On trying a couple of lists, this code can sort a reversed list but can't handle a random or ascending then descending list: trying to sort [1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1] gives [1, 1, 2, 3, 4, 5, 5, 6, 3, 4, 7, 2, 6, 7, 8, 8, 9]. Is there something simple I'm missing?</p>