Both Haskell & Arc quicksort are functional (they don't mutate their input), which means they can't have quicksort's usual O(1) additional space overhead. Their time complexity is the same, though.
In-place quicksort is most easily done with an array-like datastructure, so vectors for Arc (if they're mutable, which I think they are). It's probably possible to do it by mutating conses as well, but it would be tricky.
