About parallel merging paper...

Discussion in 'C++' started by aminer, Aug 26, 2012.

  1. aminer

    aminer Guest

    Hello,

    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+sort


    The idea is simple:

    Let's assume we want to merge sorted arrays X and Y. Select X[m] median
    element in X. Elements in X[ .. m-1] are less than or equal to X[m].
    Using binary search find index k of the first element in Y greater than
    X[m].
    Thus Y[ .. k-1] are less than or equal to X[m] as well. Elements in X[m+1
    ... ]
    are greater than or equal to X[m] and Y[k .. ] are greater. So merge(X, Y)
    can be defined as concat(merge(X[ .. m-1], Y[ .. k-1]), X[m], merge(X[m+1
    ... ], Y[k .. ]))
    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.
     
    aminer, Aug 26, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?Q2hpYXJh?=

    crystal report paper size

    =?Utf-8?B?Q2hpYXJh?=, Apr 28, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    9,833
    =?Utf-8?B?Q2hpYXJh?=
    Apr 28, 2005
  2. Soren
    Replies:
    4
    Views:
    1,304
    c d saunter
    Feb 14, 2008
  3. rickman
    Replies:
    9
    Views:
    891
    Colin Paul Gloster
    Jul 21, 2009
  4. Vivek Menon
    Replies:
    5
    Views:
    3,432
    Paul Uiterlinden
    Jun 8, 2011
  5. Vivek Menon
    Replies:
    0
    Views:
    1,787
    Vivek Menon
    Jun 10, 2011
Loading...

Share This Page