import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.RecursiveAction; public class MergeSortForkJoin { public static class MergeSortTask extends RecursiveAction { private static final long serialVersionUID = 1L; private final List<Integer> list; private final int lo; private final int hi; public MergeSortTask(List<Integer> list, int lo, int hi) { this.list = list; this.lo = lo; this.hi = hi; } @Override protected void compute() { if (lo >= hi) { return; } else { int mid = (lo + hi) / 2; MergeSortTask task1 = new MergeSortTask(list, lo, mid); MergeSortTask task2 = new MergeSortTask(list, mid+1, hi); invokeAll(task1, task2); merge(list, lo, mid, hi); } } private void merge(List<Integer> list, int lo, int mid, int hi) { List<Integer> tmp = new ArrayList<>(); for (int i : list) { tmp.add(i); } int left = lo; int right = mid + 1; int idx = lo; while (left <= mid && right <= hi) { if (tmp.get(left) <= tmp.get(right)) { Integer element = tmp.get(left); list.set(idx, element); left++; idx++; } else { Integer element = tmp.get(right); list.set(idx, element); right++; idx++; } } while (left <= mid) { Integer element = tmp.get(left); list.set(idx, element); idx++; left++; } while (right <= hi) { Integer element = tmp.get(right); list.set(idx, element); idx++; right++; } } } public static void main(String[] args) throws Exception { ForkJoinPool pool = new ForkJoinPool(); List<Integer> list = Arrays.asList(4, 9, 1, 5, 8, 0, 7, 6, 3, 2); System.out.println("Unsorted: " + list); MergeSortTask task = new MergeSortTask(list, 0, list.size()-1); try { do { pool.execute(task); } while (!task.isDone()); } finally { pool.shutdown(); } System.out.println("Sorted: " + list); } }
Monday, August 17, 2015
Parallel Merge Sort using Fork and Join
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment