Arc Forumnew | comments | leaders | submitlogin
3 points by rntz 2772 days ago | link | parent

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.