> 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

This would be the case for a pure function: http://en.wikipedia.org/wiki/Pure_function

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.

"you could accomplish the same thing by introducing a new language construct that explicitly noted that the order of two calls doesn't matter"

Effectively, this is what Golang's "go" construct does. Combined with channels you can construct an arbitrary dependency graph as well.

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?

> But don't you mean "multiple recursive calls", not specifically two?

Yes, of course.

Exercise for the non-lazy lurker: can you generalize the Quicksort algorithm based on this? Is there any benefit to doing so?

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.

> Since sorting is inherently a one-dimensional activity, I doubt it.

Imagine you had 100 billion items to sort and 10,000 cores to put to work. Would that change your answer?