How to merge sort on a dual core ?

Discussion in 'Java' started by John, Mar 10, 2008.

  1. John

    John Guest

    Hi people !!

    Do you know where i can find a merge sort source code designed for (at least 2) multi threaded environment ?
    John, Mar 10, 2008
    #1
    1. Advertising

  2. John

    Roedy Green Guest

    On Mon, 10 Mar 2008 15:57:06 +0100, John <> wrote,
    quoted or indirectly quoted someone who said :

    >Do you know where i can find a merge sort source code designed for (at least 2) multi threaded environment ?


    A simple one would just partition the data in half, sort each half on
    a separate thread, then do a final merge pass.
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Mar 10, 2008
    #2
    1. Advertising

  3. John

    Roedy Green Guest

    On Mon, 10 Mar 2008 22:07:06 GMT, Roedy Green
    <> wrote, quoted or indirectly quoted
    someone who said :

    >A simple one would just partition the data in half, sort each half on
    >a separate thread, then do a final merge pass.


    you could use Sun's sort on both halves, or any of the sorts with
    source at http://mindprod.com/jgloss/sort.html
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Mar 10, 2008
    #3
  4. John

    Roedy Green Guest

    On Mon, 10 Mar 2008 22:07:06 GMT, Roedy Green
    <> wrote, quoted or indirectly quoted
    someone who said :

    >A simple one would just partition the data in half, sort each half on
    >a separate thread, then do a final merge pass.


    A 2-way merge where you know in advance the sizes of the two inputs is
    pretty simple, but if you need inspiration see
    http://mindprod.com/products2.html#SORTED
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Mar 10, 2008
    #4
  5. John

    John Guest

    Roedy Green a écrit :
    > On Mon, 10 Mar 2008 22:07:06 GMT, Roedy Green
    > <> wrote, quoted or indirectly quoted
    > someone who said :
    >
    >> A simple one would just partition the data in half, sort each half on
    >> a separate thread, then do a final merge pass.


    Yeah that's only idea i got.

    > A 2-way merge where you know in advance the sizes of the two inputs is
    > pretty simple, but if you need inspiration see
    > http://mindprod.com/products2.html#SORTED


    There is no merge sort on your webpage.

    By "2-way merge", do you mean iterating through the 2 partition at the same time, taking the smaller of each list ?
    John, Mar 11, 2008
    #5
  6. John

    Roedy Green Guest

    On Tue, 11 Mar 2008 10:02:19 +0100, John <> wrote,
    quoted or indirectly quoted someone who said :

    >There is no merge sort on your webpage.

    There is now.

    >By "2-way merge", do you mean iterating through the 2 partition at the same time, taking the smaller of each list ?

    yes, an sequential pass interleave, what a card collating machine used
    to do in the olden days.

    A mergesort sorts bundles by any of a number of means. Then it merges
    the bundles, with very simple copy loop. The code in
    http://mindprod.com/products2.html#SORTED is full of merge loops.

    You don't use merge sorts for sorting a small number of items.
    Normally the only time you use them is for external sorts, where you
    sort ram-fulls of data, put them on disk, then read N bundles
    simultaneously sequentially and output a combined bundle, gradually
    reducing the number of bundles.

    This takes me back to the 60s when I wrote a mag tape sort.
    Back then much of your logic was about trying to get the final pass to
    come out right to land on the desired tape. You used several reels for
    scratch. It is much easier with disk, but for a fast sort, each
    scratch should be on a different physical drive.

    In your case, it is duck simple. Split your data logically in two,
    (experiment to see if copying into two separate arrays helps or
    hinders). Turn a Sun sort loose on both halves. Wait until both
    threads are done. Merge the two outputs into one, and return that
    array, or copy it back into the original with System.arraycopy.
    If you write a sort for a List, e.g. ArrayList, with proper generics,
    it will work on collections of any type that supports Comparable or
    Comparator. To see how to pull it off, have a look at the source for
    any of my sorts, or Sun’s sort.

    However, because of Java’s lack of orthogonality, your List sort won’t
    work for arrays of such Objects. You need to write very similar code
    to do that. Even that array version won’t sort an array of primitives
    such as long, int or byte. You have to write yet another slightly
    different version of the sort to handle each type of primitive.
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Mar 11, 2008
    #6
    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. Andy
    Replies:
    5
    Views:
    2,828
  2. malv

    Dual Core outlook

    malv, Feb 7, 2006, in forum: Python
    Replies:
    6
    Views:
    371
  3. robert
    Replies:
    2
    Views:
    446
  4. Simon Wittber

    Help me use my Dual Core CPU!

    Simon Wittber, Sep 12, 2006, in forum: Python
    Replies:
    23
    Views:
    753
    mystilleef
    Sep 18, 2006
  5. rkk
    Replies:
    9
    Views:
    809
    CBFalconer
    Sep 24, 2006
Loading...

Share This Page