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.