Pythonでクイックソートの実装

100個の整数からなるリストを乱数で生成して、クイックソートするコードです。
partitionを用いない単純なクイックソートで実装しました。

最後に実行時間を計測するコードをつけています。

quick_sort.py

from typing import List
import random
import time

def quick_sort(numbers: List[int]) -> List[int]:
    
    numbers_set = set(numbers)

    if len(numbers_set) <= 1:
        return numbers

    p1 = numbers[0]
    p2 = 0
    for i in range(len(numbers)):
        if numbers[i] != p1:
            p2 = numbers[i]
            break
    

    pivot = p1 if p1 > p2 else p2

    left_list = []
    right_list = []

    for i in range(len(numbers)):
        if numbers[i] < pivot:
            left_list.append(numbers[i])
        else:
            right_list.append(numbers[i])

    return quick_sort(left_list) + quick_sort(right_list)



if __name__ == "__main__":
    nums = [random.randint(0,100) for _ in range(100)]
    start = time.time()
    quick_sort(nums)
    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")