Sunday, 21 March 2021

Working Merge Sort Implementation In Java

 Here is the fully working solution of Merge Sort written in Java.


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.

No comments:

Post a comment

Evaluate Reverse Polish Notation In Java

Here is a fully working Java solution for evaluation of Reverse Polish Notation (Postfix Expression). This is a common interview question th...