Merge Sort Program in Java

The Merge Sort is a sorting algorithm which is based on the divide-and conquer approach.

It works as follows:

1. It divides a list into two halves.
2. Sort the two halves recursively using merge sort.
3. Merge the two sorted halves to form the final sorted list.

Below is the Java program that implements merge sort on a list of integers stored in an array:

import java.util.Scanner;
class MergeSort{
    int arr[];
    int capacity;
    public MergeSort(int size){
        capacity = size;
        arr = new int[capacity];
    }
    public void input(){
        Scanner in = new Scanner(System.in);
        System.out.println("Enter " + capacity + " elements:");
        for(int i = 0; i < arr.length; i++)
            arr[i] = Integer.parseInt(in.nextLine());
    }
    public void recur(int a[], int lower, int upper){
        if(lower == upper)
            return;
        else{
            int mid = (lower + upper) / 2;
            recur(a, lower, mid);
            recur(a, mid + 1, upper);
            merge(a, lower, mid + 1, upper);
        }
    }
    public void merge(int a[], int low, int high, int upper){
        int i = 0;
        int lower = low;
        int mid = high - 1;
        int n = upper - lower + 1;
        while(low <= mid && high <= upper){
            if(arr[low] < arr[high])
                a[i++] = arr[low++];
            else
                a[i++] = arr[high++];
        }
        while(low <= mid)
            a[i++] = arr[low++];
        while(high <= upper)
            a[i++] = arr[high++];
        for(i = 0; i < n; i++)
            arr[lower + i] = a[i];
    }
    public void display(){
        for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("How many elements? ");
        int num = Integer.parseInt(in.nextLine());
        MergeSort obj = new MergeSort(num);
        obj.input();
        int list[] = new int[num];
        obj.recur(list, 0, num - 1);
        System.out.print("Sorted list: ");
        obj.display();
    }
}