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?
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.)
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)
Commented
Dec 11, 2013 at 12:37
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.
Commented
Dec 11, 2013 at 16:56
Algorithms that are based on trial and error should fit your description, as the trials can be done in parallel.
Examples would be:
Leave joking:
Mergesort certainly is a good candidate to implement a parallel algorithm.
A general algorithm for parallel sorting could be like this :
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.
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.
sortworks 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).