Python練習(マージソート)

Pythonマージソート

マージソートは配列を二つに分け、各々でソートし、最後にマージしてソートする。
2つに分けた後のソートも同様な処理を再帰させて行うことができる。(分割統治法)
マージソートは同じ値が存在した場合、配列の添字の順を維持することができる。
計算量はO(NlogN)

コード(Python)

#coding: UTF-8

#マージソート

def mergesort(x, left, right):
    if right - left <= 1:
        return
    mid = left + (right - left) /2
    mergesort(x, left, mid)
    mergesort(x, mid, right)

    marge(x, left, mid, right)

def marge(x, left, mid, right):
    n = right - left

    work = [] 
    iw = 0
    il = left
    ir = mid

    #二つの配列から小さい方を選ぶ(同じ場合、1つめの配列から選ぶ)
    while il < mid and ir < right:
        if x[il] <= x[ir] :
            work.append(x[il])
            iw += 1
            il += 1
        else:
            work.append(x[ir])
            iw += 1
            ir += 1
    
    #選ばれていない要素を一時領域に入れる
    while il < mid:
        work.append(x[il])
        iw += 1
        il += 1
    while ir < right:
        work.append(x[ir])
        iw += 1
        ir += 1
    x[left:left+n] = work
    print x

x = [4,50,3,10,88,39,2,15]

mergesort(x, 0, len(x) )

print "-"*30
print x

出力

[4, 50, 3, 10, 88, 39, 2, 15]
[4, 50, 3, 10, 88, 39, 2, 15]
[3, 4, 10, 50, 88, 39, 2, 15]
[3, 4, 10, 50, 39, 88, 2, 15]
[3, 4, 10, 50, 39, 88, 2, 15]
[3, 4, 10, 50, 2, 15, 39, 88]
[2, 3, 4, 10, 15, 39, 50, 88]
------------------------------
[2, 3, 4, 10, 15, 39, 50, 88]