Merge Sort - Revisit with Fork and Join
February 23, 2015
Linear merge sort:
private int[] mergeSort(int[] input, int fromIndex, int length) {
if (length == 1)
return new int[]{input[fromIndex]};
int mid = length >>> 1;
int[] sorted1 = mergeSort(input, fromIndex, mid);
int[] sorted2 = mergeSort(input, (fromIndex + mid), (length - mid));
return merge(sorted1, sorted2);
}
private int[] merge(int[] sorted1, int[] sorted2) {
int[] merged = new int[sorted1.length + sorted2.length];
int i = 0, j = 0, k = 0;
while (i < sorted1.length && j < sorted2.length) {
if (sorted1[i] < sorted2[j])
merged[k++] = sorted1[i++];
else
merged[k++] = sorted2[j++];
}
if (i >= sorted1.length) {
while (j < sorted2.length)
merged[k++] = sorted2[j++];
} else {
while (i < sorted1.length)
merged[k++] = sorted1[i++];
}
return merged;
}
Fork and Join Merge Sort:
// Code to invoke fork and join merge sort
Will explain later ...
Fork and Join Merge Sort:
// Code to invoke fork and join merge sort
MergeSorter mg = new MergeSorter(input, 0, input.length);
ForkJoinPool pool = new ForkJoinPool();
int[] output = pool.invoke(mg2);
@Override
protected int[] compute() {
if (length == 1)
return new int[]{input[startIndex]};
int mid = length >>> 1;
MergeSorter ms1 = new MergeSorter(input, startIndex, mid);
ms1.fork();
MergeSorter ms2 = new MergeSorter(input, (startIndex + mid), (length - mid));
return merge(ms1.join(), ms2.invoke());
}
private int[] merge(int[] sorted1, int[] sorted2) {
int[] merged = new int[sorted1.length + sorted2.length];
int i = 0, j = 0, k = 0;
while (i < sorted1.length && j < sorted2.length) {
if (sorted1[i] < sorted2[j])
merged[k++] = sorted1[i++];
else
merged[k++] = sorted2[j++];
}
if (i >= sorted1.length) {
while (j < sorted2.length)
merged[k++] = sorted2[j++];
} else {
while (i < sorted1.length)
merged[k++] = sorted1[i++];
}
return merged;
}
Will explain later ...
Posted by Uday Shankar. Posted In : Java
A curious Java Developer.
