Working Merge Sort Implementation In Java

 Here is the fully working solution of Merge Sort written 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);
}
}

I didn’t write the main() method intentionally. If you want, you can write a main() method & call mergeSort(arr, 0, arr.length-1) with any custom input.

Leave a Comment