为什么这个排序算法运行不了？

Question

def f(x):
    l=[]
    r=[]
    if len(x)==1:
        return x
    if len(x)==2:
        if x[1]<x[0]:x[1],x[0]=x[0],x[1]
        return x
    else:
        for i in range(1,len(x)):
            if x[i]>x[0]:r.append(x[i])
            else:l.append(x[i])
        return f(l)+[x[0]]+f(r)

def main():
    l=[7,9,8,6,5,4]
    print(f(l))

if __name__=="__main__":main()

Answer 1

第1次对[7,9,8,6,5,4]循环后：l=[6,5,4],r=[9,8] ,return f(l)+[7]+f(r)
第1.1次[6,5,4] 循环后：l=[5,4],r=[], return f(l)+[6]+f([])
第1.2次[9,8] ,return [8,9]
第1.1.1次[5,4] ,return[4,5]

所以1.1次得结果为 [4,5,6]
所以1次 得结果为[4,5,6]+[7]+[8,9]
理论上没有错误得，但在return 过程中会发现，少了一种分析情况，f([]).
正确代码如下：

def f(x):
    l=[]
    r=[]
    if len(x)==0:
        return([])
    if len(x)==1:
        return (x)
    elif len(x)==2:
        if x[1]<x[0]:
            x[1],x[0]=x[0],x[1]
        return (x)
    else:
        for i in range(1,len(x)):
            if x[i]>x[0]:
                r.append(x[i])
            else:
                l.append(x[i])
        return (f(l)+[x[0]]+f(r))

if __name__=='__main__':
    l=[7,9,8,6,5,4]
    print(f(l))