// Quicksort on a List<Int> — Lomuto partition, recursive.
// Demonstrates: recursion with list slicing via helper, building result lists
// with push, and concatenating sublists. Pure / functional style: each call
// returns a fresh sorted list rather than mutating in place.
//
//   soma run  examples/corpus/algorithms/quicksort.cell sort "[3,6,1,8,2,9,4]"
//   soma test examples/corpus/algorithms/quicksort.cell

cell Quicksort {
    face {
        signal sort(xs: List) -> List
    }

    on sort(xs: List) {
        if len(xs) <= 1 { return xs }
        let pivot = xs[0]
        let less = list()
        let more = list()
        for i in range(1, len(xs)) {
            if xs[i] < pivot { less = push(less, xs[i]) }
            else { more = push(more, xs[i]) }
        }
        let left = sort(less)
        let right = sort(more)
        // left ++ [pivot] ++ right
        let out = push(left, pivot)
        for v in right { out = push(out, v) }
        return out
    }
}

cell test QuicksortTests {
    rules {
        assert sort([3, 6, 1, 8, 2, 9, 4])[0] == 1
        assert sort([3, 6, 1, 8, 2, 9, 4])[6] == 9
        assert to_string(sort([5, 4, 3, 2, 1])) == to_string([1, 2, 3, 4, 5])
        assert to_string(sort([2, 2, 1, 1, 3])) == to_string([1, 1, 2, 2, 3])
        assert to_string(sort(list())) == to_string(list())
        assert to_string(sort([42])) == to_string([42])
    }
}