SHOW:
|
|
- or go back to the newest paste.
1 | - | package com.rsredsq; |
1 | + | |
2 | import java.util.concurrent.RecursiveAction; | |
3 | ||
4 | public class MultiThreadedMergeSort4 { | |
5 | ||
6 | public Comparable array[]; | |
7 | ||
8 | public MultiThreadedMergeSort4(Comparable array[]) { | |
9 | this.array = array; | |
10 | } | |
11 | ||
12 | public void sort() { | |
13 | ForkJoinPool pool = new ForkJoinPool(); | |
14 | RecursiveAction start = new Sorter(0, array.length - 1); | |
15 | pool.invoke(start); | |
16 | } | |
17 | ||
18 | class Sorter extends RecursiveAction { | |
19 | public int left; | |
20 | public int right; | |
21 | ||
22 | public Sorter(int left, int right) { | |
23 | this.left = left; | |
24 | this.right = right; | |
25 | } | |
26 | ||
27 | protected void compute() { | |
28 | int i = left; | |
29 | int j = right; | |
30 | Comparable tmp; | |
31 | Comparable mid = array[(left + right) / 2]; | |
32 | ||
33 | while (i <= j) { | |
34 | while (array[i].compareTo(mid) < 0) { | |
35 | i++; | |
36 | } | |
37 | while (array[j].compareTo(mid) > 0) { | |
38 | j--; | |
39 | } | |
40 | ||
41 | if (i <= j) { | |
42 | tmp = array[i]; | |
43 | array[i] = array[j]; | |
44 | array[j] = tmp; | |
45 | i++; | |
46 | j--; | |
47 | } | |
48 | } | |
49 | ||
50 | Sorter leftTask = null; | |
51 | Sorter rightTask = null; | |
52 | ||
53 | if (left < i - 1) { | |
54 | leftTask = new Sorter(left, i - 1); | |
55 | } | |
56 | if (i < right) { | |
57 | rightTask = new Sorter(i, right); | |
58 | } | |
59 | ||
60 | if (right - left > 2) { | |
61 | if (leftTask != null && rightTask != null) { | |
62 | invokeAll(leftTask, rightTask); | |
63 | } else if (leftTask != null) { | |
64 | invokeAll(leftTask); | |
65 | } else if (rightTask != null) { | |
66 | invokeAll(rightTask); | |
67 | } | |
68 | } else { | |
69 | if (leftTask != null) { | |
70 | leftTask.compute(); | |
71 | } | |
72 | if (rightTask != null) { | |
73 | rightTask.compute(); | |
74 | } | |
75 | } | |
76 | } | |
77 | } | |
78 | } |