import java.util.Scanner;

public class MergeSort {

    // Global array `a` and auxiliary array `b`
    private static int[] a;
    private static int[] b;

    // MergeSort function
    public static void mergeSort(int low, int high) {
        if (low < high) {
            // Divide step: find the midpoint
            int mid = (low + high) / 2;

            // Solve subproblems by recursively calling mergeSort on each half
            mergeSort(low, mid);
            mergeSort(mid + 1, high);

            // Combine step: merge the two halves
            merge(low, mid, high);
        }
    }

    // Merge function to combine two sorted subarrays a[low:mid] and a[mid+1:high]
    public static void merge(int low, int mid, int high) {
        int h = low;  // Start index for first subarray
        int i = low;  // Index to place merged elements in the auxiliary array
        int j = mid + 1;  // Start index for second subarray

        // Copy the elements to the auxiliary array `b`
        b = new int[a.length];
        
        // Merge the two subarrays
        while (h <= mid && j <= high) {
            if (a[h] <= a[j]) {
                b[i] = a[h];
                h++;
            } else {
                b[i] = a[j];
                j++;
            }
            i++;
        }

        // Copy remaining elements of the first subarray (if any)
        while (h <= mid) {
            b[i] = a[h];
            h++;
            i++;
        }

        // Copy remaining elements of the second subarray (if any)
        while (j <= high) {
            b[i] = a[j];
            j++;
            i++;
        }

        // Copy the sorted elements back to the original array
        for (int k = low; k <= high; k++) {
            a[k] = b[k];
        }
    }

    // Helper method to print the array
    public static void printArray() {
        for (int element : a) {
            System.out.print(element + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a scanner object for taking input from the user
        Scanner scanner = new Scanner(System.in);

        // Ask the user for the size of the array
        System.out.println("Enter the number of elements in the array:");
        int n = scanner.nextInt();

        // Initialize the global array `a` with the user-provided size
        a = new int[n];

        // Take input from the user for the array elements
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        // Display the original array
        System.out.println("Original array:");
        printArray();

        // Sort the array using mergeSort
        mergeSort(0, a.length - 1);

        // Display the sorted array
        System.out.println("Sorted array:");
        printArray();

        // Close the scanner
        scanner.close();
    }
}



Algorithm:
 
 
 
Algorithm MergeSort(low, high)
    // a[low : high] is a global array to be sorted.
    // Small(P) is true if there is only one element to sort.
    // In this case, the list is already sorted.
 
    if (low < high) then  
        // Step 1: Divide the problem into subproblems
    {
        mid := ⌊(low + high) / 2⌋;  // Find where to split the set
        
        // Step 2: Solve the subproblems
        MergeSort(low, mid);
        MergeSort(mid + 1, high);
 
        // Step 3: Combine the solutions
        Merge(low, mid, high);
    }
}
 
 
 
Algorithm Merge (low, mid, high)
k := low; i := low; j := mid + 1;  
while ((i ≤ mid) and (j ≤ high)) do  
    if (a[i] ≤ a[j]) then  
    {  
        b[k] := a[i]; i := i + 1;  
    }  
    else  
    {  
        b[k] := a[j]; j := j + 1;  
    }  
    k := k + 1;  
}
 
if (i > mid) then  
    for k := j to high do  
    {  
        b[k] := a[k]; i := i + 1;  
    }  
else  
    for k := i to mid do  
    {  
        b[k] := a[k]; i := i + 1;  
    }  
 
for k := low to high do a[k] := b[k];  
 
 
 
OUTPUT:
Enter the size of the array: 5
Enter 5 elements:
10
3
6
2
9
Original array:
10 3 6 2 9 
Sorted array:
2 3 6 9 10