Following is the java implementation of the algorithm in java.
public class MergeSort {
public MergeSort(Integer a[]) {
this.a = a;
}
Integer a[];
public void merge(int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
Integer L[] = new Integer[n1 + 1];
Integer R[] = new Integer[n2 + 1];
for (int i = 0; i < n1; i++) {
L[i] = a[p + i];
}
for (int j = 0; j < n2; j++) {
R[j] = a[q + j + 1];
}
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
for (int k = p; k <= r; k++) {
if (L[i] < R[j]) {
a[k] = L[i];
i = i + 1;
} else {
a[k] = R[j];
j = j + 1;
}
}
}
public void mergeSortPass(int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSortPass(p, q);
mergeSortPass(q + 1, r);
merge(p, q, r);
}
}
public void mergeSort() {
mergeSortPass(0, a.length - 1);
}
}
JUnit test for MergeSort
import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;
public class MergeSortTest {
private Integer[] numbers;
private final static int SIZE = 7;
private final static int MAX = 20;
@Test
public void testMergeSort() {
for (int i = 0; i < 200; i++) {
numbers = new Integer[SIZE];
Random generator = new Random();
for (int a = 0; a < numbers.length; a++) {
numbers[a] = generator.nextInt(MAX);
}
Integer copy[]=new Integer[SIZE];
System.arraycopy(numbers, 0, copy, 0, numbers.length);
MergeSort ms=new MergeSort(numbers);
ms.mergeSort();
Arrays.sort(copy);
assertArrayEquals(copy, numbers);
}
}
}
Reference- Introduction To Algorithms
0 comments:
Post a Comment