# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The /compare page's recursive merge sort on lists.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_le

# from study/compare/recursion/merge_sort.viv: merge merge_sort

def merge(a, b) {
    out = []
    i = 0
    j = 0
    while i < len(a) and j < len(b) {
        if lg_le(a[i], b[j]) {
            out = append(out, a[i])
            i += 1
        }
        else {
            out = append(out, b[j])
            j += 1
        }
    }
    out = extend(out, a[i:])
    out = extend(out, b[j:])
    return out
}

def merge_sort(xs) {
    if len(xs) <= 1 {
        return xs
    }
    mid = len(xs) // 2
    return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:]))
}