Java Program to Implement Merge Sort Algorithm

May 30, 2023

What is a Sorting?

In the Article, we will write a Program to Implement the Merge Sort and discuss the Implementation of the Merge Sort Algorithm.
Sorting algorithms are used to rearrange the items in a list or array so that they are in a specific order. There are many different sorting algorithms, each with its own set of trade-offs in terms of efficiency, speed, and complexity. Some common sorting algorithms include bubble sort, insertion sort, selection sort, merge sort, quick sort, and heap sort.

Sorting in Java:

In Java, there are several ways to sort elements:

Using the sort() method of the java.util.Arrays class: This method sorts the elements of an array in ascending order. It can be used to sort arrays of primitive data types (such as int, char, etc.) as well as arrays of objects (such as String, etc.).
Using the Collections.sort() method: This method sorts the elements of a List in ascending order. It can be used to sort Lists of objects (such as ArrayList, LinkedList, etc.).
Using a sorting algorithm: There are several sorting algorithms that you can use to sort elements in Java. Some of the commonly used sorting algorithms are:
1. Bubble sort
2. Insertion sort
3. Selection sort
4. Merge sort
5. Quick sort

Here is an example of how you can Implement the Merge Sort Algorithm.

Pseudo Code For Merge Sort Implementation:

MergeSort(int[] A, int start, int end)
    if start < end then
        int middle = (start + end) / 2
        
        // recursively sort left subarray
        MergeSort(A, start, middle)         
        
        // recursively sort right subarray
        MergeSort(A, middle + 1, end)     
        
        // merge the two sorted subarrays
        Merge(A, start, middle, end)          

Merge(int[] A, int start, int middle, int end)
    // size of left subarray
    int n1 = middle - start + 1             
    // size of right subarray
    int n2 = end - middle                 
    
    // create left subarray
    int[] Left = new int[n1 + 1]      
    // create right subarray
    int[] Right = new int[n2 + 1]      

    // copy left subarray into L
    for i = 0 to n1 - 1 do         
        Left[i] = A[start + i]
        
    // copy right subarray into R    
    for j = 0 to n2 - 1 do         
        Right[j] = A[m + j + 1]
    Left[n1] = INFINITY               
    Right[n2] = INFINITY               

    int i = 0, j = 0
    
    // merge the two subarrays into A
    for k = start to end do              
        if Left[i] <= Right[j] then
            A[k] = Left[i]
            i = i + 1
        else
            A[k] = Right[j]
            j = j + 1

Program For Merge Sort Implementation:

Run

import java.util.*;

public class Main{
    public static void mergeSort(int[] arr, int start, int end) {
        if (start < end) {
            
            // Middle element
            int mid = (start + end) / 2;
            
            // merge left side
            mergeSort(arr, start, mid);
            
            // merge right side
            mergeSort(arr, mid + 1, end);
            
            // merge both sides
            merge(arr, start, mid, end);
        }
    }
    public static void merge(int[] arr, int start, int mid, int end) {
        int n1 = mid - start + 1;
        int n2 = end - mid;

        int[] L = new int[n1 + 1];
        int[] R = new int[n2 + 1];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[start + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + j + 1];
        }

        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;

        int i = 0, j = 0;
        for (int k = start; k <= end; k++) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 5, 1, 9, 3, 7, 4, 8, 6, 2 };
        System.out.println("Original array: " + Arrays.toString(arr));

        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Output:
Original array: [5, 1, 9, 3, 7, 4, 8, 6, 2]
Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Explanation: The mergeSort method takes in an integer array arr, and the start and end indices of the subarray being sorted. It first checks if the subarray has more than one element, and if so, it computes the middle index mid and recursively calls mergeSort on the left and right halves of the subarray. It then calls the merge method to merge the two sorted halves back together.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others