Java Program to Implement Merge Sort

Introduction

Merge Sort is a popular and efficient sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the array into two halves until each sub-array contains a single element and then merging the sub-arrays back together in a sorted order. This guide will walk you through writing a Java program that implements the Merge Sort algorithm.

Problem Statement

Create a Java program that:

Prompts the user to enter the size of an array and its elements.
Sorts the array using the Merge Sort algorithm.
Displays the sorted array.

Example:

Input: [38, 27, 43, 3, 9, 82, 10]
Output: "Sorted array: [3, 9, 10, 27, 38, 43, 82]"

Solution Steps

Read the Array Size and Elements: Use the Scanner class to take the size and elements of the array as input from the user.
Implement Merge Sort: Use recursion to divide the array and merge the sub-arrays in a sorted manner.
Display the Sorted Array: Print the sorted array.

Java Program

// Java Program to Implement Merge Sort
// Author: https://www.rameshfadatare.com/

import java.util.Scanner;

public class MergeSort {
    public static void main(String[] args) {
        // Step 1: Read the size and elements of the array from the user
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("Enter the size of the array: ");
        int size = scanner.nextInt();
        
        int[] array = new int[size];
        
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < size; i++) {
            array[i] = scanner.nextInt();
        }
        
        // Step 2: Sort the array using Merge Sort
        mergeSort(array, 0, size - 1);
        
        // Step 3: Display the sorted array
        System.out.println("Sorted array:");
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
    }
    
    // Method to implement Merge Sort
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            // Find the middle point
            int middle = left + (right - left) / 2;
            
            // Sort the first half
            mergeSort(array, left, middle);
            
            // Sort the second half
            mergeSort(array, middle + 1, right);
            
            // Merge the sorted halves
            merge(array, left, middle, right);
        }
    }
    
    // Method to merge two halves
    public static void merge(int[] array, int left, int middle, int right) {
        // Find sizes of two sub-arrays to be merged
        int n1 = middle - left + 1;
        int n2 = right - middle;
        
        // Create temporary arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];
        
        // Copy data to temporary arrays
        for (int i = 0; i < n1; i++) {
            leftArray[i] = array[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArray[i] = array[middle + 1 + i];
        }
        
        // Merge the temporary arrays
        
        // Initial indexes of first and second sub-arrays
        int i = 0, j = 0;
        
        // Initial index of merged sub-array
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        
        // Copy remaining elements of leftArray[] if any
        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        
        // Copy remaining elements of rightArray[] if any
        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

Explanation

Step 1: Read the Array Size and Elements

The Scanner class is used to read the size of the array and its elements. The nextInt() method captures the size and each element.

Step 2: Implement Merge Sort

mergeSort Method:
- This method recursively divides the array into two halves.
- It finds the middle index, recursively sorts the left half, and then the right half.
- Finally, it merges the two halves back together in sorted order using the merge method.
merge Method:
- This method merges two sub-arrays into a single sorted array.
- It creates two temporary arrays (leftArray and rightArray) to hold the values of the two halves.
- It then compares the elements of the two arrays and arranges them in sorted order back into the original array.

Step 3: Display the Sorted Array

The sorted array is printed using a for loop.

Output Example

Example 1:

Enter the size of the array: 7
Enter the elements of the array:
38 27 43 3 9 82 10
Sorted array:
3 9 10 27 38 43 82

Example 2:

Enter the size of the array: 5
Enter the elements of the array:
12 11 13 5 6
Sorted array:
5 6 11 12 13

Conclusion

This Java program demonstrates how to implement the Merge Sort algorithm to sort an array. Merge Sort is an efficient, stable, and comparison-based sorting algorithm that is particularly useful for large datasets. The program covers key concepts such as recursion, array manipulation, and the divide-and-conquer strategy, making it a valuable exercise for those learning Java programming.