Notebooks · lib/algo/legacy/seq_argsort

lib/algo/legacy/seq_argsort.viv

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 1–41

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The merge-sort argsort every TheAlgorithms port uses (seq.viv); it shadows the builtin there.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_le

# from study/idioms/thealgorithms-python/seq.viv: argsort

#| The indices that sort `keys` ascending, ties kept in input order
#| (Python `sorted(range(n), key=keys.__getitem__)`): a bottom-up merge sort.
def seq_argsort(keys: Arr) -> Arr {
    n = len(keys)
    idx = zeros(n)
    tmp = zeros(n)
    for i to n {
        idx[i] = i
    }
    width = 1.0
    while width < n {
        lo = 0.0
        while lo < n {
            mid = min(lo + width, n)
            hi = min(lo + 2.0 * width, n)
            i = lo
            j = mid
            for k to hi - lo {
                if i < mid and (j >= hi or lg_le(keys[idx[i]], keys[idx[j]])) {
                    tmp[lo + k] = idx[i]
                    i = i + 1.0
                }
                else {
                    tmp[lo + k] = idx[j]
                    j = j + 1.0
                }
            }
            lo = hi
        }
        idx[:] = tmp
        width = 2.0 * width
    }
    return idx
}

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The merge-sort argsort every TheAlgorithms port uses (seq.viv); it shadows the builtin there.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_le

# from study/idioms/thealgorithms-python/seq.viv: argsort

#| The indices that sort `keys` ascending, ties kept in input order
#| (Python `sorted(range(n), key=keys.__getitem__)`): a bottom-up merge sort.
def seq_argsort(keys: Arr) -> Arr {
    n = len(keys)
    idx = zeros(n)
    tmp = zeros(n)
    for i to n {
        idx[i] = i
    }
    width = 1.0
    while width < n {
        lo = 0.0
        while lo < n {
            mid = min(lo + width, n)
            hi = min(lo + 2.0 * width, n)
            i = lo
            j = mid
            for k to hi - lo {
                if i < mid and (j >= hi or lg_le(keys[idx[i]], keys[idx[j]])) {
                    tmp[lo + k] = idx[i]
                    i = i + 1.0
                }
                else {
                    tmp[lo + k] = idx[j]
                    j = j + 1.0
                }
            }
            lo = hi
        }
        idx[:] = tmp
        width = 2.0 * width
    }
    return idx
}