Working Merge Sort Implementation In Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.*;
import java.lang.*;
import java.io.*;


class Solution
{
    void merge(int arr[], int l, int m, int r)
    {
        int[] leftArr = new int[m - l + 1];
        int[] rightArr = new int[r - m];
        for(int i=l; i<= m; i++){
            leftArr[i-l] = arr[i];
        }
        for(int i=m+1; i<=r; i++){
            rightArr[i-(m+1)] = arr[i];
        }
        int x = 0;
        int y = 0;
        int i = l;
        while(x < leftArr.length && y < rightArr.length){
            if(leftArr[x] > rightArr[y]){
                arr[i] = rightArr[y];
                y++;
            } else {
                arr[i] = leftArr[x];
                x++;
            }
            i++;
        }
        while(x < leftArr.length){
            arr[i] = leftArr[x];
            x++;
            i++;
        }
        while(y < rightArr.length){
            arr[i] = rightArr[y];
            y++;
            i++;
        }
    }
    void mergeSort(int arr[], int l, int r)
    {
        if(l >= r){
            return;
        }
        int m = l + (r-l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}