Merge Sort

import java.util.Scanner;

public class Merge {
    public void merge(int arr[], int l, int m, int r) {
        int[] left = new int[m - l + 1];
        int[] right = new int[r - m];
        
        // Copy data into left[] and right[]
        System.arraycopy(arr, l, left, 0, left.length);
        System.arraycopy(arr, m + 1, right, 0, right.length);

        int i = 0, j = 0, k = l;
        
        // Merge the left and right arrays back into arr[]
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements of left[], if any
        while (i < left.length) {
            arr[k++] = left[i++];
        }

        // Copy remaining elements of right[], if any
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public void sort(int arr[], int l, int r) {
        if (l < r) {
            int mid = (l + r) / 2;
            sort(arr, l, mid);
            sort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }
    }

    public static void display(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Prompt user for array size
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();

        // Create array and input elements
        int[] arr = new int[n];
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println("Original array:");
        display(arr);
        
        // Perform merge sort
        new Merge().sort(arr, 0, arr.length - 1);
        
        System.out.println("Sorted array:");
        display(arr);

        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;  
end  

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