// Merge sort on a List<Int> — top-down, purely functional.
// Demonstrates: splitting a list into halves, recursive sort, and the
// two-pointer merge of two sorted lists into one. Stable and O(n log n).
//
//   soma run  examples/corpus/algorithms/merge_sort.cell sort "[38,27,43,3,9,82,10]"
//   soma test examples/corpus/algorithms/merge_sort.cell

cell MergeSort {
    face {
        signal sort(xs: List) -> List
        signal merge_lists(a: List, b: List) -> List
    }

    // NOTE: named merge_lists, not merge — `merge` is a builtin (map union)
    // that would shadow a handler called from a test cell.
    on merge_lists(a: List, b: List) {
        let out = list()
        let i = 0
        let j = 0
        while i < len(a) && j < len(b) {
            if a[i] <= b[j] {
                out = push(out, a[i])
                i = i + 1
            } else {
                out = push(out, b[j])
                j = j + 1
            }
        }
        while i < len(a) {
            out = push(out, a[i])
            i = i + 1
        }
        while j < len(b) {
            out = push(out, b[j])
            j = j + 1
        }
        return out
    }

    on sort(xs: List) {
        let n = len(xs)
        if n <= 1 { return xs }
        let mid = floor(n / 2)
        let left = list()
        let right = list()
        for i in range(0, mid) { left = push(left, xs[i]) }
        for i in range(mid, n) { right = push(right, xs[i]) }
        return merge_lists(sort(left), sort(right))
    }
}

cell test MergeSortTests {
    rules {
        assert to_string(sort([38, 27, 43, 3, 9, 82, 10])) == to_string([3, 9, 10, 27, 38, 43, 82])
        assert to_string(sort([5, 4, 3, 2, 1])) == to_string([1, 2, 3, 4, 5])
        assert to_string(merge_lists([1, 3, 5], [2, 4, 6])) == to_string([1, 2, 3, 4, 5, 6])
        assert to_string(sort(list())) == to_string(list())
        assert to_string(sort([1])) == to_string([1])
        assert len(merge_lists([1, 2], list())) == 2
        assert merge_lists([1, 2], list())[0] == 1
        assert merge_lists([1, 2], list())[1] == 2
    }
}