cp_library/alg/iter/sort/sort_parallel_fn.py

View this file on GitHub
Last update: 2025-06-20 03:24:59+09:00

Depends on

Code

import cp_library.__header__
import cp_library.alg.__header__
import cp_library.alg.iter.__header__
from cp_library.alg.iter.arg.argsort_fn import argsort
import cp_library.alg.iter.sort.__header__

def sort_parallel(*L: list, reverse=False):
    N, K, order = len(L[0]), len(L), argsort(L[0], reverse)
    R = tuple([0]*N for _ in range(K))
    for k, Lk in enumerate(L):
        Rk = R[k]
        for i, j in enumerate(order): Rk[i] = Lk[j]
    return R

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''




def argsort(A: list[int], reverse=False):
    s, m = pack_sm(len(A))
    if reverse:
        I = [a<<s|m^i for i,a in enumerate(A)]
        I.sort(reverse=True)
        for i,ai in enumerate(I): I[i] = m^ai&m
    else:
        I = [a<<s|i for i,a in enumerate(A)]
        I.sort()
        for i,ai in enumerate(I): I[i] = ai&m
    return I


def pack_sm(N: int): s=N.bit_length(); return s,(1<<s)-1


def sort_parallel(*L: list, reverse=False):
    N, K, order = len(L[0]), len(L), argsort(L[0], reverse)
    R = tuple([0]*N for _ in range(K))
    for k, Lk in enumerate(L):
        Rk = R[k]
        for i, j in enumerate(order): Rk[i] = Lk[j]
    return R