1public class MergeSort {
2
3    void merge(int arr[], int left, int mid, int right) {
4        int n1 = mid - left + 1;
5        int n2 = right - mid;
6        int L[] = new int[n1];
7        int R[] = new int[n2];
8
9        for (int i = 0; i < n1; i++)
10            L[i] = arr[left + i];
11        for (int j = 0; j < n2; j++)
12            R[j] = arr[mid + 1 + j];
13
14        int i = 0, j = 0;
15        int k = left;
16        while (i < n1 && j < n2) {
17            if (L[i] <= R[j]) {
18                arr[k] = L[i];
19                i++;
20            } else {
21                arr[k] = R[j];
22                j++;
23            }
24            k++;
25        }
26
27        while (i < n1) {
28            arr[k] = L[i];
29            i++;
30            k++;
31        }
32
33        while (j < n2) {
34            arr[k] = R[j];
35            j++;
36            k++;
37        }
38    }
39
40    void mergeSort(int arr[], int left, int right) {
41        if (left < right) {
42            int mid = left + (right - left) / 2;
43            mergeSort(arr, left, mid);
44            mergeSort(arr, mid + 1, right);
45            merge(arr, left, mid, right);
46        }
47    }
48
49    public static void main(String args[]) {
50        int arr[] = {12, 11, 13, 5, 6, 7};
51
52        MergeSort ob = new MergeSort();
53        ob.mergeSort(arr, 0, arr.length - 1);
54
55        System.out.println("Sorted array:");
56        for (int i = 0; i < arr.length; i++)
57            System.out.print(arr[i] + " ");
58    }
59}

1import