2

After googling for a couple hours, I came to a conclusion that all sorting algorithms are inherently sequential which can be data distributed but not task distributable.

Is there any algorithm which is not inherently sequential and is task distributable?

  • What do you mean by task distributable? – dan_waterworth Dec 11 '13 at 11:43
  • @dan_waterworth: algorithm capable of exhibiting functional parallelism. – Knight Rider Dec 11 '13 at 11:48
  • Does mergesort fit your criteria? – dan_waterworth Dec 11 '13 at 11:55
  • @dan_waterworth : it exhibits data parallelism. Since, Same operation is done on different parts of data. – Knight Rider Dec 11 '13 at 12:02
  • 1
    Huh? A merge-sort seems quite parallelizable to me: parts of the data can be pre-sorted in different threads/nodes and then combined in another one (compare also how the command-line sort works for large inputs). Usually, the pre-sort will have to complete before the merge, but that could be changed as well (consider a moronic sort algorithm that yields the minimal element in a collection and removes it until no elements are left). – amon Dec 11 '13 at 12:57
13

You overlooked sleep-sort which is task distributed. Here is an implementation for the Bourne shell:

input="10 4 5 1"
for n in $input; do
  (sleep $n; echo $n) &
done

When the program completes, the sorted list of numbers is printed on the standard output. (Note that you could need to add job management to determine when the subprocesses finish.)

  • I love that one ^^ works only for small integers, but definitely something new, to me :) +1 for originality – Olivier Dulac Dec 11 '13 at 12:29
  • could be adapted in C to sleep n microseconds (or nanoseconds, if possible).. as long as it is sure to wake-up-and-write with enough time to not overlap each others, it could make for an interresting and fast sorting algorithm for integers when they are over a 10^6 or even 10^9 range... – Olivier Dulac Dec 11 '13 at 12:30
  • And it made me think : why not "grep sort" ? put a bunch of grep '^$n$' in background, reading on, say, fd 3, and output on fd 3 the list of integers from 0 to 10^9 : As soon as one sees it's number, it outputs it (as it grep's it). No need to wait 1 second between each numbers (but may need some sort of wait, otherwise job management could not output the proper grep in the right order all the time) (and need to be able to have several process read on the same fd) – Olivier Dulac Dec 11 '13 at 12:37
  • 1
    @OlivierDulac There is race conditions with this method, because processes do not need to be rescheduled after each line. – user40989 Dec 11 '13 at 15:11
  • my "grep sort" is not good either: can't have many process reading on same fd. But it could be done this way (memory/cpu expensive, but almost "linear") : 1) have the list in a file, one number per line 2) for i in $(seq 0 100000); do grep "^${i}$" file ; done [this, like your answer, also keep tracks of multiple numbers of the same value.]. I prefer the sleep sort as it doesn't depend on any limit (apart the time it takes.... which can be huge). grep sort would be much faster, but would miss any numbers outside its range. – Olivier Dulac Dec 11 '13 at 16:56
3

Algorithms that are based on trial and error should fit your description, as the trials can be done in parallel.

Examples would be:

  • Bogosort, which shuffles the data until it's sorted

  • StackSort, which looks for sort algorithms on stackoverflow, running them one by one until a correct answer is returned

3

Leave joking:
Mergesort certainly is a good candidate to implement a parallel algorithm.

A general algorithm for parallel sorting could be like this :

  1. Divide the data in k junks (where k is the number of processing agents).
  2. Sort each junk in parallel.
  3. Merge the sorted junks.

As @amon points out in his comment, the third step can even be executed partly in parallel with step 2, if the sort algorithm selected returns the small elements first.

2

See Knuth's discussion of polyphase merge sort with replacement selection in volume 2 of ACP. Or google "external sort". These sorts go way back to the early days of computing when computers often didn't have enough memory to sort all the data, but had multiple tape drives attached. If you replace tape drives with inter-process data flows, the algorithms still work wonderfully. I implemented this algorithm in the early 1980s for a system that did not have an OS-supplied sorting program.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.