Merge Sort | Java

 Merge Sort  | Java

This Java code implements the Merge Sort algorithm to sort an array of integers in ascending order. Let's break down the code step by step:

mergeSort class: The code is organized inside a class named mergeSort.

PrintArr method: This method takes an array arr as input and prints its elements separated by space. It's used to print the elements of the array after sorting.

merge method: This method is responsible for merging two sorted subarrays into one sorted array. It takes four parameters:

arr: The array containing elements to be merged.

f: The index of the first element of the first subarray.

mid: The index marking the end of the first subarray and the start of the second subarray.

l: The index of the last element of the second subarray.

The method initializes three iterators i, j, and k to iterate through the left subarray, right subarray, and the temporary array respectively. It creates a temporary array tempArr to store the merged result. Then, it compares elements from the left and right subarrays, and copies the smaller element into tempArr. After copying, it increments the iterators accordingly. Finally, it copies the remaining elements from both subarrays into tempArr, and then copies the sorted elements back into the original array arr.

mergeSort method: This is the recursive function that implements the merge sort algorithm. It takes three parameters:

arr: The array to be sorted.

f: The index of the first element of the subarray to be sorted.

l: The index of the last element of the subarray to be sorted.

It first checks if f is greater than or equal to l, which means the subarray has only one element or no elements, so it's already sorted, and it returns. Otherwise, it calculates the middle index mid. Then, it recursively calls mergeSort for the left half and the right half of the array, and then calls merge to merge the sorted halves.

main method: This is the entry point of the program. It initializes an array arr with some integers, calculates the length of the array, calls mergeSort to sort the array, and then calls PrintArr to print the sorted array.

package Merge;

public class mergeSort {

    public static void merge(int arr[], int f, int mid, int l) {

        int i = f; // iterator for left part

        int j = mid + 1; // iterator for right part

        int k = 0; // iterator for temp

        int tempArr[] = new int[l - f + 1]; // for stored copyied data

        while (i <= mid && j <= l) {

            if (arr[i] < arr[j]) {

                tempArr[k] = arr[i];

                i++;

            } else {

                tempArr[k] = arr[j];

                j++;

            }

            k++;

        }

        // left side----

        while (i <= mid) {

            tempArr[k++] = arr[i++];

        }

        // right side---

        while (j <= l) {

            tempArr[k++] = arr[j++];

        }

        // copy data

        for (k = 0, i = f; k < tempArr.length; k++, i++) {

            arr[i] = tempArr[k];

        }

    }

    public static void mergesrt(int arr[], int f, int l) {

        if (f >= l) {

            return;

        }

        int mid = (f + l) / 2;

        System.out.println(mid);

        mergesrt(arr, f, mid);

        mergesrt(arr, mid + 1, l);

        merge(arr, f, mid, l);

    }

    public static void main(String[] args) {

        int arr[] = { 8, 7, 6, 5 };

        int n = arr.length - 1;

        mergesrt(arr, 0, n);

        PrintArr(arr);

    }

    public static void PrintArr(int arr[]) {

        for (int i = 0; i < arr.length; i++) {

            System.out.print(arr[i] + " ");

        }

        System.out.println();

    }

}