Pythonで基本的なソート

Pythonとアルゴリズムの勉強のために基本的なソートを書きました。
気が向いたら今後も追加していきます。

#選択ソート (selection sort)

def sSort(a):
    for i in range(len(a)-1):
        mi = a[i:].index(min(a[i:]))
        a[i], a[i+mi] = a[i+mi], a[i]
    
    return a

#バブルソート (bubble sort)

def bSort(a):
    for i in range(len(a)):
        for j in range(len(a)-1, i, -1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
            
    return a

#挿入ソート (insertion sort)

def iSort(a):
    for i in range(1, len(a)):
        for j in range(i, 0, -1):
            if a[j] >= a[j-1]:
                break
            else:
                a[j], a[j-1] = a[j-1], a[j]
    
    return a

#クイックソート (quick sort)

def qSort(a):
    if len(a) in (0, 1):
        return a
    
    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

    return qSort(l) + [p] + qSort(r)

#マージソート (merge sort)

def merge(l, r):
    n = len(l + r) # マージ後の配列のサイズ
    s = max(l + r) + 1 # 番兵

    l.append(s)
    r.append(s)

    a = []
    while len(a) < n:
        a.append(l.pop(0)) if l[0] <= r[0] else a.append(r.pop(0))
    
    return a

def mSort(a):
    if len(a) == 1:
        return a

    mid = len(a) // 2
    l = mSort(a[:mid])
    r = mSort(a[mid:])
    
    return merge(l, r)