Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development Topics
- Intel® Moderncode for Parallel Architectures
- About parallel merging ...

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

aminer10

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

08-26-2012
11:49 AM

57 Views

About parallel merging ...

I have just read the following paper on Parallel
Merging:

http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf

And
i have implemented this algorithm just to see what is the
performance.

And i have noticed that the serial algorithm is 8 times
slower

than the merge function that you find in the serial mergesort
algorithm.

So 8 times slower, it's too slow.

It's better to use the
following
algorithm;

http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=parallel%2Bsort

The
idea is simple:

Let's assume we want to merge sorted arrays X and Y.
Select X

element in X. Elements in X[ .. m-1] are less than or
equal to X

Using binary search find index k of the first element in Y
greater than

X

Thus Y[ .. k-1] are less than or equal to X

are greater than or equal to X

can be defined as concat(merge(X[ .. m-1], Y[ ..
k-1]), X

now we can recursively in parallel
do merge(X[ .. m-1], Y[ .. k-1]) and

merge(X[m+1 .. ], Y[k .. ]) and then
concat results.

And then you can continue to apply this method
recursivily.

Thank you,

Amine Moulay Ramdane.

Link Copied

2 Replies

Andrey_Tikhonov

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-25-2012
12:38 AM

57 Views

Very interesting, thank you.

SergeyKostrov

Valued Contributor II

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

01-13-2013
02:45 PM

57 Views

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.