A slow... very slow sorting algorithm

benchmark.txt

1 => 1 ------------------------------------------------------
< Min                   0.00001 |                         1 | 0.00x
> Max                   0.00003 |                         1 | 0.00x
~ Avg                   0.00001 |                       1.0 | 0.00x
2 => 1 ------------------------------------------------------
< Min                   0.00001 |                         1 | 1.00x
> Max                   0.00030 |                        30 | 29.07x
~ Avg                   0.00004 |                      8.48 | 4.17x
3 => 1 ------------------------------------------------------
< Min                   0.00003 |                         2 | 0.61x
> Max                   0.00851 |                     1,464 | 194.70x
~ Avg                   0.00119 |                    191.46 | 27.29x
4 => 1 ------------------------------------------------------
< Min                   0.00155 |                       151 | 1.30x
> Max                   0.21055 |                    21,929 | 176.56x
~ Avg                   0.06305 |                   6,407.3 | 52.87x
5 => 1 ------------------------------------------------------

sort.py

import random
from time import perf_counter
from typing import Callable, List, Tuple, NoReturn

SortFunc = Callable[[List[int]], List[int]]


def unrecursify(func: SortFunc) -> SortFunc:
    class Unrecursify(Exception):
        pass

    call_args: List[Tuple[int]] = []

    def inner(*args: int) -> NoReturn:
        call_args.append(args)
        raise Unrecursify()

    def wrapper(*args: int) -> Tuple[List[int], int]:
        bak: SortFunc = func
        globals()[func.__name__] = inner
        call_args.append(args)
        
        while True:
            try:
                r = bak(*call_args[-1])
                globals()[func.__name__] = unrecursify(bak)
                return r
            except Unrecursify:
                continue

    return wrapper


@unrecursify
def sort(lst: List[int]) -> List[int]:
    if not lst:  # 0 length elimination
        return lst

    # Build a list using "last survivors" method
    out: List[int] = []
    for i in range(len(lst)):
        c_lst = lst.copy()
        while len(c_lst) > 1:
            i = random.randint(0, len(c_lst) - 1)
            x, c_lst = c_lst[i], c_lst[:i] + c_lst[i + 1:]
        out.extend(c_lst)  # We extend the list by 1 each time
    
    # Checking sort using min check value
    m = out[0]
    for i in out[1:]:
        if i < m:
            return sort(lst)
        m = i

    # Checking for the out list to be a relpica of the given list
    c_out: List[int] = out.copy()
    for k in lst:
        i = random.randint(0, len(c_out) - 1)
        x, c_out = c_out[i], c_out[:i] + c_out[i + 1:]

        if x != k:
            return sort(lst)

    return out


def main():
    to_sort = [4, 3, 2, 1]

    marker = perf_counter()
    sorted_list = sort(to_sort)
    elapsed = perf_counter() - marker

    print(f'Sorted sorted_list {elapsed * 1000:,.2f}ms')
    
    
if __name__ == '__main__':
    main()