algorithm - クイックソート

Median Sort と基本的な方法は同じ。
Median を選ばず適当な位置をピボットに配列を分割する。
ワーストケースパフォーマンスを避けるために単純なランダムでないバリエーションもある。
(Median-of-three 等)
配列が小さい時は挿入ソートの方が速くなるので、 サイズが一定以下になったら挿入ソートを使う。

def selectPivotIndex(left, right):
    return random.randint(left, right + 1)

# 配列を、pivotIndex の値で分割する。
# pivotIndex の値より小さい値は前、
# pivotIndex の値より大きい値は後ろに移動
def partition(arr, comp_func, left, right, pivotIndex):
    # pivot の値を最後尾に移動
    pivot = arr[pivotIndex]
    tmp = arr[right]
    arr[right] = pivot
    arr[pivotIndex] = tmp
    
    # pivot より小さい値を前に持っていく
    store = left
    for i in range(left, right):
        if comp_func(arr[i], pivot) < 0:
            tmp = arr[i]
            arr[i] = arr[store]
            arr[store] = tmp
            store += 1
    # pivot を配置
    tmp = arr[store]
    arr[store] = pivot
    arr[right] = tmp
    return store

# 挿入ソート
def insertion(arr, comp_func, left, right):
    for i in range(left, right + 1):
        tmp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] >= tmp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = tmp

# 最大深さを記録。特に意味は無い。
max_depth = 0
# 配列サイズがこれ以下なら挿入ソートを使う
MIN_SIZE = 4

def qsort(arr, comp_func, left, right, depth):
    if right <= left:
        return
    pivotIndex = selectPivotIndex(left, right)
    pivotIndex = partition(arr, comp_func, left, right, pivotIndex)
    # サイズが一定以下なら挿入ソート
    if pivotIndex <= MIN_SIZE:
        # グローバル変数にアクセスするには global 宣言が必要
        global max_depth
        max_depth = max(max_depth, depth)
        insertion(arr, comp_func, left, pivotIndex - 1)
    else:
        qsort(arr, comp, left, pivotIndex - 1, depth + 1)
    if right - pivotIndex - 1 <= MIN_SIZE:
        global max_depth
        max_depth = max(max_depth, depth)
        insertion(arr, comp_func, pivotIndex + 1, right)
    else:
        qsort(arr, comp, pivotIndex + 1, right, depth + 1)

a = range(1, 500)
random.shuffle(a)

print a

qsort(a, comp, 0, len(a) - 1, 0)

print max_depth
print a