Question

IN JAVA

write a program that asks a user for a maximum of 20 user-inputted elements and create an array. Then, write a Merge Sort function with recursion (in the main) that takes the user inputted elements in the array, sorts them, and prints them back.

Answer 1

The following is the program that allows user to input upto 20 elements and get it merge sorted. The program is commented side by side to the code for better understanding.

import java.util.Scanner;

public class HelloWorld{
    // Merge function that merges two sorted arrays.
    // Time complexity : O(N)
    // Space complexity: O(N)
    static void merge(int[] arr, int l, int m, int r)
    {
        // Create an array to hold elements that are inserted while
        // sorting in merge.
        int mergeOut[] = new int[r-l+1];
        int i=l, j=m+1; //Seggregate input array into left and right parts.
        int x = 0; // Pointer to start of output array.
        for(; i<=m && j<=r;){
          // Adds elements from left/right part based on which is smaller
          // in the given instant. Smaller one of the left and right side
          // is added and the pointer is incremented.
            if(arr[i]<arr[j]){
                mergeOut[x++] = arr[i++];
            } else {
                mergeOut[x++] = arr[j++];
            }
        }
        // Adds remaining elements in left side.
        while(i<=m){
            mergeOut[x++] = arr[i++];
        }
        // Adds remaining elements in right side.
        while(j<=r){
            mergeOut[x++] = arr[j++];
        }
        // Copies output array to input array.
        for(j=l, i=0; j<=r; i++, j++){
            arr[j] = mergeOut[i];
        }
    }
    // MergeSort: Divide and Conquer Algorithm
    // Time complexity : O(NLogN)
    // Space Complexity : O(N)
    static void mergeSort(int[] arr, int l, int r)
    {
        if (l < r)
        {
            int m = l+(r-l)/2;
            mergeSort(arr, l, m);
            mergeSort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
    // Prints resultant array.
    // Time complexity : O(N)
    // Space complexity : O(1)
    static void printArray(int[] arrayEl){
        System.out.println("Sorted Array: ");
        for(int i=0; i<arrayEl.length; i++){
            System.out.print(arrayEl[i]+" ");
        }
        System.out.println("");
    }
    public static void main(String []args){
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the number of elements to be sorted");
        int elementCount = scanner.nextInt();
        if(elementCount>20){
            System.out.println("ERROR!! Enter less than 20 elements");
            return;
        }
        int arrayEl[] = new int[elementCount];
        System.out.println("Enter elements to be sorted");
        for(int i=0; i<arrayEl.length; i++){
            int temp = scanner.nextInt();
            System.out.println("Input element: " + temp);
            arrayEl[i] = temp;
        }
        mergeSort(arrayEl, 0, elementCount-1);
        printArray(arrayEl);
     }
}