Note that 'partition returns (true-elements false-elements). It could reasonably go the other way around.
As the first blog commenter notes, "I believe that that commonly cited example of quicksort in Haskell is not really quicksort, in that it does not have the space and time complexity of quicksort." This is probably true of these Arc snippets as well. Could we get a "real" Arc quicksort?
Also, none of these implementations is a stable sort.
I believe this is a "real" qsort. It's way more verbose than I expected, but I did code it on two nights hours after I should have gone to bed. I'm sure I could name some things better. Maybe I will later.
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.
I chose to ignore the pedantry on what is and isn't a quicksort :) Hoare's original algorithm has been mutated several times, and I think it's subjective which of those mutations deserves the name and which doesn't. Especially in high-level languages that encourage programmers to ignore low level concerns of space usage. Wikipedia calls the copying version a 'simple' quicksort (http://en.wikipedia.org/wiki/Quicksort#Simple_version), so I went with that title. I think it's equally valid to call the in-place quicksort a destructive quicksort, like the difference between reverse and nreverse in Common Lisp.