Quick sort where space order is O(1)

gistfile1.py

# coding: utf-8
import random
 
def quick_sort(inlist, first, last):
    if last - first < 1:
        return inlist
    pivot = inlist[first]
    left, right = first, last
    while left != right:
        if inlist[right] >= pivot:
            right -= 1
        elif inlist[left] < pivot:
            left += 1
        else:
            inlist[right], inlist[left] = inlist[left], inlist[right]
    # right equals left
    middle = right
    inlist = quick_sort(inlist, first, middle)
    inlist = quick_sort(inlist, middle+1, last)
    return inlist

これ、pivotにとった数が複数あると無限ループになりそうですね。

なっちゃいそうだね。

    if inlist[right] >= pivot:
        right -= 1
    elif inlist[left] < pivot:
        left += 1

ってだけで、うまくいくと思う

update しました。