Sorting with Multiple Threads

Question

I am trying to sort a number of integers using 4 threads, splitting the array and then recombining. I think I have accomplished using 2 threads, can anyone help from here how i'd move up to using 4?

import java.util.Random;
import java.util.Arrays;

public class threadSort implements Runnable {
private static final int L = 64;
private static int[] nums;
private static Random rand;

public void run() {
    //sorting upper half
    Arrays.sort(nums, nums.length/2, nums.length);
}

public static void main(String args[]) throws InterruptedException {

    nums = new int[L];
    rand = new Random();

    //fill the array
    for(int i=0; i<nums.length; i++) {
        nums[i] = rand.nextInt(10);
    }

    Thread t = new Thread(new threadSort());
    t.start();

    //sorting lower half
    Arrays.sort(nums, 0, nums.length/2);

    t.join();

    /* merge */
    int j = 0;
    int k = nums.length/2; 
    int[] tmp = new int[nums.length];
    for (int i=0; i<tmp.length; i++){
        if (j < nums.length/2) {
            if (k < nums.length) {
                if (nums[j] < nums[k]) {
                    tmp[i] = nums[j++];
                } else {
                    tmp[i] = nums[k++];
                }
            } else {
                /* reached end of second half, copy first*/
                tmp[i] = nums[j++];
            }
        } else {
            /* reached end of 1st half, copy 2nd*/
            tmp[i] = nums[k++];
        }
    }
    nums = tmp;


    //Testing Sort and Total
    int count = 0;

    for(int i=0; i<nums.length; i++){
    System.out.print(nums[i] + " ");
    count++;
    }
    System.out.println();
    System.out.println("Total amount of Integers = " + count);
}

}

thats what i have so far I want to stick with what i have but throw 2 more threads in

I would recommend a recursive approach to allow for arrays of indefinite size. — Christian Mann
– Christian Mann, Commented Nov 9, 2010 at 3:52
I hope this is for homework or personal education. Sorting 64 elements is typically (depending on Comparator implementation) such a trivial operation that the overhead in creating Threads and synchronizing the memory model should far outweigh any performance gain. — Tim Bender
– Tim Bender, Commented Nov 10, 2010 at 2:07

Jeremy · Accepted Answer · 2010-11-09 03:56:11Z

1

The best way is to use forkjoin. Basically you recursively divide your data into binary chunks until you have a small enough chunk you want to work with. Using DL's forkjoin framework is a fun exercise, but if you want to keep it simple, read on.

All you need to do is call your current algorithm twice. That is, use it to break your data in half. Then call your algorithm on each half. When both of those are done, merge their results.

answered Nov 9, 2010 at 3:56

Jeremy

22.5k4 gold badges71 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Tim Bender Over a year ago

+1, but... Does Doug Lea go by DL now? General FYI, ForkJoin is a part of Java 7's concurrency package (from what I've seen).

Jeremy Over a year ago

DL was my professor at college. And yes, it is targeted to be in Java 7. See: cs.oswego.edu/pipermail/concurrency-interest/2010-September/…

Collectives™ on Stack Overflow

Sorting with Multiple Threads

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related