Python中快速排序优化探究：为何效率不及插入排序？

我了解到快速排序是最高效的排序算法之一，但我实现及测试的版本却表现缓慢。我已查阅过十年前的相关问答，但其答案均未做优化。我测试了多个答案的代码，发现都效率低下，于是自行实现了一个初步优化的版本：

import random
from collections import deque

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x >= arr[0]])

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    lt = deque()
    ge = deque()
    e0 = arr.popleft()
    for e in arr:
        if e < e0:
            lt.append(e)
        else:
            ge.append(e)
    return quick_sort(lt) + deque([e0]) + quick_sort(ge)

def quick_sort_helper(arr):
    return quick_sort(deque(arr))

order = list(range(256))
chaos = random.choices(range(666), k=256)

测试结果：

In [2]: %timeit qsort(chaos)
480 µs ± 2.83 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [3]: %timeit qsort(order)
4.05 ms ± 45.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [4]: %timeit quick_sort_helper(chaos)
394 µs ± 9.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [5]: %timeit quick_sort_helper(order)
3.06 ms ± 57.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

测试结果显示这些快速排序版本都极慢，我的优化仅带来小幅提升。作为对比，我快速实现的插入排序版本性能反而更优：

def bisect_right(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

def insertion_sort(arr):
    out = deque()
    for e in arr:
        out.insert(bisect_right(out, e), e)
    return out

测试结果：

In [12]: %timeit insertion_sort(chaos)
311 µs ± 6.28 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [13]: %timeit insertion_sort(order)
267 µs ± 7.93 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

此外，我测试了评论中链接的另一答案代码，其性能也未超过我的版本，仅在最坏情况表现稍好：

In [22]: %timeit qsort(chaos, 0, 255)
391 µs ± 6.95 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [28]: %timeit qsort(order, 0, 255)
360 µs ± 6.43 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

请问如何通过减少递归、识别有序子序列来优化快速排序算法，消除不必要的计算？

内容的提问来源于stack exchange，提问作者Ξένη Γήινος