from typing import List


def quick_sort(source) -> List[int]:
    """クイックソート. 計算量: O(n log n)"""
    if len(source) <= 1:
        return source

    n = len(source)

    # いったん中央の値を求める
    median_value = source[n // 2]

    # 分割する領域を作成
    smalls, bigs, middles = [], [], []

    # データソースの値を、3つの領域に振り分ける
    for i in range(n):
        if source[i] < median_value:
            smalls.append(source[i])
        elif source[i] > median_value:
            bigs.append(source[i])
        else:
            middles.append(source[i])

    # 大小が発生した領域を更に分割する
    if smalls:
        smalls = quick_sort(smalls)

    if bigs:
        bigs = quick_sort(bigs)

    # 極限まで分割した各領域を合成する
    return smalls + middles + bigs