/**
 * Java implementation of merge sort
 *
 * @author Carlos Abraham Hernandez 
 * @email  abraham@abranhe.com
 */

import java.util.Arrays;

public class MergeSort {

    // Merge the two half into a sorted data.
    public void merge(int arr[], int left, int middle, int right) {

        int n1 = middle - left + 1;
        int n2 = right - middle;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[middle + 1 + j];

        int i = 0, j = 0;

        int k = left;
        while (i < n1 && j < n2) {
            if (L[i]