4 ms·

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

by theoh 12y ago

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?

lisper 12y ago
> 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?
- theoh 12y ago
  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.
  - lisper 12y ago
    > 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?
- comex 12y ago
  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.

by theoh 12y ago

lisper 12y ago

> 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?

theoh 12y ago
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.
- lisper 12y ago
  > 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?
comex 12y ago
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.