0

I am on a mission of sorting somewhat large array of unsigned, 64-bit, randomly generated integers (over 5E7 elements). Can you direct me to a parallel sorting algorithm that might exhibit almost linear speedup at least in the case of random data?

I am working with Java, in case it makes any difference with regard to fast sorting.

Edit: Note that this question is primarily concerned with parallel sorts capable to achieve near-linear speedup. (Meaning, when the amount of executing cores grows from P to 2P, the time spent by a parallel sort drops to 55 - 50 percent of the computation performed on P cores.)

coderodde
  • 1,269
  • 4
  • 17
  • 34
  • Something you want to implement or already implemented? Former, may be a merge-sort? – Nim Mar 20 '12 at 15:01
  • btw - this question may help: http://stackoverflow.com/questions/2210185/correctly-multithreaded-quicksort-or-mergesort-algo-in-java – Nim Mar 20 '12 at 15:02
  • 1
    When searching for better performance, it might be useful to know what performance you have now, and what your goal is. Can you post some numbers on how long, say, `Arrays.sort()` takes, and what speed you want to achieve? – Eli Acherkan Mar 20 '12 at 15:04
  • it has been a bit but isnt 5e7 == 5^7 ? – Woot4Moo Mar 20 '12 at 15:04
  • @josefx thanks I knew I was missing something – Woot4Moo Mar 20 '12 at 15:07

5 Answers5

0

Bitonic sort is an algorithm targeted for parallel machines. Here is a sequential Java version and a parallel C++ version to help you get started.

shams
  • 3,460
  • 24
  • 24
0

Well if you got a lot of memory you can use Bucketsort. One other algorithm that goes well with parallelism is Quicksort

nist
  • 1,706
  • 3
  • 16
  • 24
0

From the Wikipedia article on Quicksort,

Like merge sort, quicksort can also be parallelized due to its divide-and-conquer nature. Individual in-place partition operations are difficult to parallelize, but once divided, different sections of the list can be sorted in parallel. The following is a straightforward approach: If we have processors, we can divide a list of elements into sublists in O(n) average time, then sort each of these in average time. Ignoring the O(n) preprocessing and merge times, this is linear speedup. If the split is blind, ignoring the values, the merge naïvely costs O(n). If the split partitions based on a succession of pivots, it is tricky to parallelize and naïvely costs O(n). Given O(log n) or more processors, only O(n) time is required overall, whereas an approach with linear speedup would achieve O(log n) time for overall.

Obviously mergesort is another alternative. I think quicksort gives better average-case performance.

smessing
  • 4,330
  • 1
  • 22
  • 19
0

Quicksort and merge sort are both fairly easy to parallelize. Oracle has a fork/join-based integer merge sort here, which you could probably use (if not as-is, then at least as inspiration).

gustafc
  • 28,465
  • 7
  • 73
  • 99
  • These "easy to parallelize" versions of Merge-/Quicksort are "naïvely" parallel as their respective Merge-/Partition-routines are after all serial, and do not provide good results according my tests. – coderodde Mar 20 '12 at 15:13
0

Say you have a few computers (5 on amazon cluster right?) and you want ascending sorting. Split your array into smaller chunks so it fits on each machine. Assuming you have n chunks/arrays. Have each machine quicksort its chunk. This sorting will be in parallel (more or less depending on chunk size and machine speed etc).

When done sorintg, have the machines merge the chunks;

You can do this in 2 ways:

  • 2 machines at a time (you're building a merge tree). The merging will happen, again, in parallel. The problem is that the array will grow big due to merging and you have to cache to disk, so when you merge again the machine reads from disk. So some penalty here.
  • You can do n machines at a time. Have one coordinator machine which takes the min from all the other machines' arrays. This way the coordinator machine builds the entire sorted array by taking the smallest number from each of the other sorted arrays.
Adrian
  • 5,603
  • 8
  • 53
  • 85