Merge Sort implementation java

Merge sort is a sorting algorithm that splits the collection into two halves and sorts each half and then merging the two halves. Consider the following example.


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: