forked from slgobinath/Java-Helps-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMultiThreadArraySort.java
More file actions
116 lines (103 loc) · 3.16 KB
/
Copy pathMultiThreadArraySort.java
File metadata and controls
116 lines (103 loc) · 3.16 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.Random;
import java.util.concurrent.*;
/**
* Example of Merge Sort using multi threads.
* This is an example of bad practice.
* The result will be MemoryOutFfErrors.
*
* @author L.Gobinath
*/
public class MultiThreadArraySort {
// From Java 7 '_' can be used to separate digits.
public static final int ARRAY_SIZE = 10_000_000;
public static void main(String[] args) {
int[] array = createArray(ARRAY_SIZE);
long startTime;
long endTime;
MergeSort mergeSort = new MergeSort(array, 0, array.length - 1);
startTime = System.currentTimeMillis();
mergeSort.start();
try {
mergeSort.join(); // waiting for other threads to complete
} catch (InterruptedException ex) {}
endTime = System.currentTimeMillis();
System.out.println("Time taken: " + (endTime - startTime) + " millis"); // 22439 millis
}
/**
* Create an array with random numbers.
* @param size Size of the array.
* @return An array with the given size.
*/
private static int[] createArray(final int size) {
int[] array = new int[size];
Random rand = new Random();
for (int i = 0; i < size; i++) {
array[i] = rand.nextInt(1000);
}
return array;
}
}
/**
* MergeSort is a sub class of Thread.
*/
class MergeSort extends Thread {
private int array[];
private int left;
private int right;
public MergeSort(int[] array, int left, int right) {
this.array = array;
this.left = left;
this.right = right;
}
@Override
public void run() {
if (left < right) {
int mid = (left + right) / 2;
// Create two new threads
Thread leftSort = new MergeSort(array, left, mid);
Thread rightSort = new MergeSort(array, mid + 1, right);
// Start the threads
leftSort.start();
rightSort.start();
try {
leftSort.join(); // Wait until left thread ends
} catch (InterruptedException ex) {}
try {
rightSort.join(); // Wait until right thread ends
} catch (InterruptedException ex) {}
merge(left, mid, right);
}
}
/**
* Merge two parts of an array in sorted manner.
* @param left Left side of left array.
* @param mid Middle of separation.
* @param right Right side of right array.
*/
private void merge(int left, int mid, int right) {
int temp [] = new int[right - left + 1];
int x = left;
int y = mid + 1;
int z = 0;
while (x <= mid && y <= right) {
if (array[x] <= array[y]) {
temp[z] = array[x];
z++;
x++;
} else {
temp[z] = array[y];
z++;
y++;
}
}
while (y <= right) {
temp[z++] = array[y++];
}
while (x <= mid) {
temp[z++] = array[x++];
}
for (z = 0; z < temp.length; z++) {
array[left + z] = temp[z];
}
}
}