TL;DR: if you have an algorithm that makes two recursive calls and it doesn't matter what order you do them in (e.g. Quicksort) then you can rewrite that algorithm to use a set of sub-problems in stead of a stack of sub-problems. The latter is what you (implicitly) get when you write an algorithm recursively.
A much more interesting observation would have been to note that you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter. That would allow a compiler to automatically produce code that used a set-of-intervals data structure, or -- much more relevant in today's world -- code that used multiple cores. (But that would have defeated the real purpose of the article, which was to be a tacit plug for Eiffel, which doesn't have such a construct.)
> A much more interesting observation would have been to note that you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter
One of the selling points of pure functional languages is the potential optimizations the compiler can theoretically do, including using multiple cores to evaluate a program, without any explicit hints from the programmer.
A very common need is to do an bunch of independent RPCs. Small wish: Allow returning values from a goroutine, along the lines of "results <- go rpc(args)".
That's a good observation. It should go without saying that recursion can always be expressed iteratively. Lamport is inclined to make observations like this, e.g. his sequential consistency concept which states that concurrency is always equivalent to a serial process. But don't you mean "multiple recursive calls", not specifically two?
You can if the partition uses new storage rather than swapping in-place (which is likely what you want anyway for horizontal parallelism, see below): pick multiple pivots and insert elements into a bucket depending on how many pivots they're greater than. This turns out to be called samplesort, with some extra detail regarding picking the buckets.
However, once you give up on in-place you should probably use radix sort instead, as long as your elements, or their hashes, have some semblance of uniform distribution: this avoids having to calculate greater-than on a large number of pivots, although depending on the architecture it may be possible to do the latter reasonably quickly, and I suppose you may end up saturating memory bandwidth anyway...
Anyway, you can run a single partition in parallel - just not in place - by dividing the input data and having separate output queues per core. You probably need to merge the buckets back into the original array anyway, so this doesn't hurt; even if you want to keep the buckets separated (but individually contiguous) for some reason, e.g. if you don't need the final output as an array and want to save some difficult-to-parallelize merging, it just makes the partition a bit trickier with some atomic stuff.
Since sorting is inherently a one-dimensional activity, I doubt it. Philosophically speaking, binary cuts are associated with qualitative phenomena, hot and cold being one of the prototypes (light and dark is another).
Bergson or Deleuze elevate this kind of thing to a metaphysical level but I think there's an underlying simplistic aspect to it. Someone gives you a line, there's not much you can do but split it into two parts.
A much more interesting observation would have been to note that you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter. That would allow a compiler to automatically produce code that used a set-of-intervals data structure, or -- much more relevant in today's world -- code that used multiple cores. (But that would have defeated the real purpose of the article, which was to be a tacit plug for Eiffel, which doesn't have such a construct.)