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

1. Read the Array Size and Elements: Use the Scanner class to take the size and elements of the array as input from the user.
2. Implement Merge Sort: Use recursion to divide the array and merge the sub-arrays in a sorted manner.
3. 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.