mergesort.java

import java.util.Scanner;

class merge_sort
{

    void merge(int arr[],int low,int high){
        if(low<high)
        {
            int mid = low + (high-low)/2;
            merge(arr,low,mid);
            merge(arr,mid+1,high);
            merging(arr, low, high, mid);
        }
    }

    void merging(int arr[],int low,int high, int mid){
        int leftSize = mid - low + 1;
        int rightSize = high - mid;

        int left[] = new int[leftSize];
        int right[] = new int[rightSize];

        for (int i = 0; i < leftSize; i++)
            left[i] = arr[low + i];
        for (int j = 0; j < rightSize; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = low;

        while (i < leftSize && j < rightSize) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < leftSize) {
            arr[k++] = left[i++];
        }

        while (j < rightSize) {
            arr[k++] = right[j++];
        }
    }
}

public class mergesort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter limit of array");
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.print("Sorted Array:");
        merge_sort m = new merge_sort();
        m.merge(arr,0, n-1);
        for(int num: arr){
            System.out.print(num + " ");
        }
        sc.close();
    }
}