Skip to content

Instantly share code, notes, and snippets.

@larsr
Last active December 11, 2015 03:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save larsr/4537928 to your computer and use it in GitHub Desktop.
Save larsr/4537928 to your computer and use it in GitHub Desktop.
def quicksort(l):
work = [(0,len(l)-1)]
while work:
(left,right) = work.pop()
if right < left:
continue
i_piv = left
piv = l[i_piv]
l0,r0 = left, right
while left<right:
while l[left] <= piv and left < right: left += 1
while l[right] > piv: right -= 1
if left < right: l[left], l[right] = l[right], l[left]
l[i_piv], l[right] = l[right], piv
work.append((l0,right-1))
work.append((right+1,r0))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment