Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-02-29
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
This note makes an observation that significantly simplifies previous parallel, two-way merge algorithms based on binary search and sequential merge in parallel. First, it is shown that the additional merge step of distinguished elements as found in previous algorithms is not necessary, thus simplifying the implementation and reducing constant factors. Second, by fixating the requirements to the binary search, the merge algorithm becomes stable, provided that the sequential merge subroutine is stable. The stable, parallel merge algorithm can easily be used to implement a stable, parallel merge sort. For ordered sequences with $n$ and $m$ elements, $m\leq n$, the simplified merge algorithm runs in $O(n/p+\log n)$ operations using $p$ processing elements. It can be implemented on an EREW PRAM, but since it requires only a single synchronization step, it is also a candidate for implementation on other parallel, shared-memory computers.
No associations
LandOfFree
Simplified, stable parallel merging does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Simplified, stable parallel merging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simplified, stable parallel merging will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-524380