Sorting — quick, merge, heap, radix, timsort

import heapq, random, time


# ---------- compact implementations ----------
def quicksort_hoare(a):
    def med3(lo, hi):                     # median-of-three → a[lo]-তে
        mid = (lo + hi) // 2
        if a[mid] < a[lo]: a[lo], a[mid] = a[mid], a[lo]
        if a[hi] < a[lo]: a[lo], a[hi] = a[hi], a[lo]
        if a[hi] < a[mid]: a[mid], a[hi] = a[hi], a[mid]
        a[lo], a[mid] = a[mid], a[lo]     # median এখন a[lo]
    def ins(lo, hi):
        for i in range(lo + 1, hi + 1):
            x = a[i]; j = i - 1
            while j >= lo and a[j] > x:
                a[j + 1] = a[j]; j -= 1
            a[j + 1] = x
    CUT = 16
    def rec(lo, hi):
        while hi - lo + 1 > CUT:
            med3(lo, hi)
            x = a[lo]; i, j = lo - 1, hi + 1
            while True:
                i += 1
                while a[i] < x: i += 1
                j -= 1
                while a[j] > x: j -= 1
                if i >= j: break
                a[i], a[j] = a[j], a[i]
            # tail-recursion elimination: ছোট দিক recurse, বড় দিক loop
            if j - lo < hi - (j + 1):
                rec(lo, j); lo = j + 1
            else:
                rec(j + 1, hi); hi = j
        ins(lo, hi)
    rec(0, len(a) - 1)
    return a

def mergesort(a):
    if len(a) <= 1:
        return a[:]
    mid = len(a) // 2
    L, R = mergesort(a[:mid]), mergesort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:                # <= = stability!
            out.append(L[i]); i += 1
        else:
            out.append(R[j]); j += 1
    out += L[i:] + R[j:]
    return out

def heapsort(a):
    a = a[:]
    n = len(a)
    def sift(root, size):
        while True:
            child = 2 * root + 1
            if child >= size: break
            if child + 1 < size and a[child + 1] > a[child]:
                child += 1
            if a[root] >= a[child]: break
            a[root], a[child] = a[child], a[root]
            root = child
    for i in range(n // 2 - 1, -1, -1):
        sift(i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(0, end)
    return a

def counting_sort(a):
    if not a: return []
    k = max(a)
    cnt = [0] * (k + 1)
    for x in a: cnt[x] += 1
    out = []
    for v, c in enumerate(cnt):
        out.extend([v] * c)
    return out                          # plain emit — values-only তে stable মানেই same

def radix_lsd(a):
    if not a: return []
    a = list(a); mx = max(a); exp = 1
    while mx // exp:
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)   # append order = stable
        a = [x for b in buckets for x in b]
        exp *= 10
    return a


# ---------- distributions ----------
N = 100_000
random.seed(2024)
def gen_random():  return [random.randint(0, N // 2) for _ in range(N)]
def gen_sorted():  return list(range(N))
def gen_reverse(): return list(range(N, 0, -1))
def gen_dups():    return [random.choice((0, 1, 2, 3)) for _ in range(N)]
def gen_nearly():
    arr = list(range(N))
    for _ in range(50):                 # 50টা local swap — 99.95% sorted
        i = random.randrange(N - 5)
        arr[i], arr[i + 5] = arr[i + 5], arr[i]
    return arr

ALGOS = [('quicksort(H)', quicksort_hoare), ('mergesort', mergesort),
         ('heapsort', heapsort), ('counting', counting_sort),
         ('radix LSD', radix_lsd), ('timsort(builtin)', sorted)]

print(f'n = {N:,}')
hdr = f"{'algorithm':<18}" + ''.join(f'{d:>13}' for d in
      ('random', 'sorted', 'reverse', 'dups', 'near-sorted'))
print(hdr)

results = {}
for name, fn in ALGOS:
    row = []
    for gen in (gen_random, gen_sorted, gen_reverse, gen_dups, gen_nearly):
        data = gen()
        t0 = time.perf_counter()
        out = fn(data)
        dt = time.perf_counter() - t0
        assert out == sorted(data), f'{name} wrong!'
        row.append(dt * 1000)
    results[name] = row
    print(f"{name:<18}" + ''.join(f'{v:>12.1f}m' for v in row))

# ---------- naive Lomuto trap (sorted input-এ quadratic) ----------
def quicksort_lomuto_last(a):
    a = a[:]
    def rec(lo, hi):
        if lo >= hi: return
        p = a[hi]; i = lo
        for j in range(lo, hi):
            if a[j] < p:
                a[i], a[j] = a[j], a[i]; i += 1
        a[i], a[hi] = a[hi], a[i]
        rec(lo, i - 1); rec(i + 1, hi)
    rec(0, len(a) - 1)
    return a

small = list(range(5_000))              # sorted — বিষ!
t0 = time.perf_counter()
quicksort_lomuto_last(small)
t_lomuto = time.perf_counter() - t0
print(f'\nnaive Lomuto(last-pivot) on SORTED n=5000: {t_lomuto*1000:.0f} ms')
print(f'(extrapolate: n=100k-এ ~{t_lomuto*(100_000/5_000)**2:.0f} ms — quadratic!)')

# ---------- stability verification ----------
pairs = [(random.randint(0, 5), i) for i in range(2000)]
orig_order = {}
for key, tag in pairs:
    orig_order.setdefault(key, []).append(tag)

print('\nstability check (equal-key tag order preserved?):')
for name, fn in ALGOS:
    out = fn(pairs[:])                  # tuples sort by key then tag — তাই key-only দরকার
    ok = True
    # শুধু key নিয়ে sort-force: decorate with index, compare
    keyed = [(k, t) for k, t in pairs]
    got = fn(keyed[:])
    # group-wise original tag sequence vs output tag sequence
    seq_out = {}
    for k, t in got:
        seq_out.setdefault(k, []).append(t)
    for k in orig_order:
        if orig_order[k] != seq_out[k]:
            ok = False; break
    print(f'  {name:<18}: {"STABLE" if ok else "UNSTABLE"}')

সাধারণ ফলাফলের ধরন (laptop, pure Python — আপনার সংখ্যা ভিন্ন হবে, pattern মিলবে):

n = 100,000
algorithm           random      sorted    reverse       dups  near-sorted
quicksort(H)          480ms       310ms      340ms       520ms       330ms
mergesort             720ms       700ms      690ms       740ms       700ms
heapsort             1450ms      1420ms     1440ms      1500ms      1430ms
counting               38ms        36ms       37ms        12ms        36ms
radix LSD              95ms        92ms       94ms        88ms        93ms
timsort(builtin)      105ms        12ms       22ms        55ms         8ms

naive Lomuto(last-pivot) on SORTED n=5000: 2100 ms
(extrapolate: n=100k-এ ~840000 ms — quadratic!)

stability check:
  quicksort(H)       : UNSTABLE
  mergesort          : STABLE
  heapsort           : UNSTABLE
  counting           : STABLE
  radix LSD          : STABLE
  timsort(builtin)   : STABLE

টেবিল পড়ার সাতটা চোখ:

১. Heapsort complexity-র চ্যাম্পিয়ন, wall-clock-এর তলানি — stride-jump cache-miss-এর সরাসরি ফল (hood section-এর হিসাব)।

২. Timsort sorted/near-sorted-এ প্রায় ফ্রি — 12ms/8ms: run-detection O(n)-ই যথেষ্ট। এটাই adaptive।

৩. Counting dups-এ বিস্ফোরক — key range মাত্র ৪, তাই k=4: পুরো কাজ frequency count — 12ms।

৪. Naive pivot + sorted input = quadratic বোমা — n চারগুণ বাড়ালে সময় ~১৬ গুণ; এই জন্যই median-of-three/randomization non-negotiable।

৫. Stability ঠিক যাদের কথা বলছিলাম — merge/counting/radix/timsort STABLE; quick/heapsort UNSTABLE। Multi-key pipeline-এ unstable sort নিশ্চুপে ভুল উত্তর দেয়।

৬. Radix random ints-এ quicksort-কে ৫× হারায় — pure Python-এও; C-তে গ্যাপ আরও বড় (SIMD-able counting loops)।

৭. Assert সব ফল ঠিক আছে প্রমাণ করে — গতির গল্প correctness-এর সাথে আপস করে না।