Merge Sort in Java

June 10, 2025

Merge Sort in Java : Detailed Explanation with Code

In this article, we will explore Merge Sort in Java programming. We will cover its working, algorithm, implementation, and complexity analysis.

Sorting is one of the most important operations in computer science and software development. It helps organize data and improve efficiency in many applications. Among the various sorting algorithms, Merge Sort stands out for its consistent performance and use of the divide and conquer strategy.

What is Merge Sort?

Merge Sort is a divide and conquer algorithm.

It works by dividing the array into smaller subarrays, sorting them individually, and then merging them to produce a sorted array.
Merge Sort was invented by John von Neumann in 1945. It is known for its stable sorting behavior and predictable performance, even in worst case scenarios.

How Merge Sort Works ?

Merge Sort works in three main steps:

Divide: Split the array into two halves recursively.
Conquer: Sort each half recursively.
Merge: Combine the sorted halves into one sorted array.

Recursion continues until each subarray has only one element. Then, it merges the sorted parts one by one.

Algorithm of Merge Sort

Here’s a step by step breakdown of the Merge Sort algorithm:

1. If the array has more than one element:

Find the middle index of the array.
Divide the array into two halves: left and right.
Recursively call Merge Sort on both halves.
Merge the sorted halves.

2. If the array has only one element, it is already sorted.

Pseudocode:

mergeSort(arr, left, right)
    if left < right
        mid = (left + right) / 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)

Bubble Sort

Selection Sort

Insertion Sort

Quick Sort

Counting Sort

Dynamic Programming

Learn DSA

Implementation of Merge Sort in Java Programming

Code:

Run

public class MergeSort {

    // Function to sort the array using merge sort
    public void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // Find the middle point
            int mid = left + (right - left) / 2;

            // Sort first and second halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    // Function to merge two subarrays of arr[]
    public void merge(int[] arr, int left, int mid, int right) {
        // Find sizes of two subarrays to be merged
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temp arrays
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // Copy data to temp arrays
        for (int i = 0; i < n1; i++)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArray[j] = arr[mid + 1 + j];

        // Merge the temp arrays

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of leftArray
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        // Copy remaining elements of rightArray
        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    // Utility method to print the array
    public void printArray(int[] arr) {
        for (int value : arr)
            System.out.print(value + " ");
        System.out.println();
    }

    // Main method to test the algorithm
    public static void main(String[] args) {
        MergeSort ms = new MergeSort();
        int[] arr = { 12, 11, 13, 5, 6, 7 };

        System.out.println("Original array:");
        ms.printArray(arr);

        ms.mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted array:");
        ms.printArray(arr);
    }
}

Explanation of the Merge Sort Code:

mergeSort() – This is the main recursive method. It splits the array and calls itself on both halves.
merge() – This method merges two sorted subarrays. It uses temporary arrays to store elements during merging.
printArray() – A utility function to display the array.
main() – This method sets up an example array, applies merge sort, and prints the results.

Space Complexity: Space Complexity: O(n)

Time Complexity: Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)

Program for Merge Sort in Java

In Java, there are two common ways to implement the Merge Sort algorithm.

Both methods follow the same core logic of divide and conquer, but they differ slightly in how they handle the arrays during the merging process:

Method 1: Using Two Separate Subarrays:
- In this method, we create two temporary subarrays, one for the left half and one for the right half of the main array.
- These subarrays are used to hold the elements before merging them back in sorted order. This method makes the merging step clearer and easier to follow, especially for beginners.
Method 2: Using a Single Array with Index Ranges
- This variation performs the same operations, but instead of creating two separate subarrays, it works with a single array by tracking the start and end indices.
- This helps reduce some overhead in terms of copying data, but the logic can be a bit more complex.

Space complexity is the same i.e. O(n) in both cases as even though there are two subarrays in method 1 they in total have n array items and method 2 also with one single array also has n array items.

Two SubArrays

One Subarray

Two SubArrays

Run

//Java Program for Merge Sort
class Main {
    // this function display the array
    public static void display(int[] arr, int size)
    {
        for(int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    // main function of the program
    public static void main(String[] args)
    {
        int[] a = {12, 8, 4, 14, 36, 64, 15, 72, 67, 84};

        int size = a.length;
        display(a, size);

        mergeSort(a, 0, size - 1);
        display(a, size);
    }

    // this function apply merging and sorting in the array
    static void mergeSort(int[] a, int left, int right)
    {
        int mid;
        if(left < right)
        {
            // can also use mid = left + (right - left) / 2
            // this can avoid data type overflow
            mid = (left + right) / 2;

            // recursive calls to sort first half and second half sub-arrays
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }
    // after sorting this function merge the array
    static void merge(int[] arr, int left, int mid, int right)
    {
        int i, j, k;
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // create temp arrays to store left and right sub-arrays
        int L[] = new int[n1];
        int R[] = new int[n2];

        // Copying data to temp arrays L[] and R[]
        for (i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        // here we merge the temp arrays back into arr[l..r]
        i = 0; // Starting index of L[i]
        j = 0; // Starting index of R[i]
        k = left; // Starting index of merged sub-array

        while (i < n1 && j < n2)
        {
            // place the smaller item at arr[k] pos
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
        // Copy the remaining elements of L[], if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        // Copy the remaining elements of R[], if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

Output

12 8 4 14 36 64 15 72 67 84 
4 8 12 14 15 36 64 67 72 84

One Subarray

Run

//Java Program for Merge Sort
class Main {
    // this function display the array
    public static void display(int[] arr, int size)
    {
        for(int i = 0; i < size; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    // main function of the program
    public static void main(String[] args)
    {
        int[] a = {12, 8, 4, 14, 36, 64, 15, 72, 67, 84};
        
        int size = a.length;
        display(a, size);

        mergeSort(a, 0, size - 1);
        display(a, size);
    }

    // this function apply merging and sorting in the array
    static void mergeSort(int[] a, int left, int right)
    {
        int mid;
        if(left < right)
        {
            // can also use mid = left + (right - left) / 2
            // this can avoid data type overflow
            mid = (left + right) / 2;

            // recursive calls to sort first half and second half sub-arrays
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }
    // after sorting this function merge the array
    static void merge(int[] a, int left, int mid, int right)
    {
        int i = left; // starting index of left sub-array
        int j = mid + 1; // starting index of right sub-array
        int index = left; // used to place items in temp[]
        int[] temp = new int[10];

        while(i <= mid && j <= right) 
        {
            // place the smaller item at temp[index]
            if(a[i] < a[j]) { temp[index] = a[i]; i = i + 1; } else { temp[index] = a[j]; j = j + 1; } index++; } // i > mid would mean all items for left
        // sub-array were successfully placed, and there
        // must be unplaced right sub-array items
        if(i > mid)
        {
            while(j <= right) {
                temp[index] = a[j];
                index++;
                j++;
            }
        }
        else {
            while(i <= mid)
            {
                temp[index] = a[i];
                index++;
                i++;
            }
         }
        int p = left;

        while(p < index)
        {
            a[p] = temp[p];
            p++;
        }
    }
}

Output

12 8 4 14 36 64 15 72 67 84 
4 8 12 14 15 36 64 67 72 84

Advantages of Merge Sort

Stable Sort – It maintains the order of equal elements.
Predictable Performance – Always runs in O(n log n) time.
Useful for Linked Lists – Does not require random access.
Efficient for Large Data – Performs better than bubble or insertion sort on large datasets.

Disadvantages of Merge Sort

Uses Extra Space – Not ideal for memory constrained systems.
Slower on Small Data – For small arrays, insertion sort can be faster.
Complex Implementation – More complex than simple sorting methods.

Conclusion

Merge Sort is a powerful and efficient sorting algorithm based on the divide and conquer principle. Its predictable O(n log n) time complexity makes it a great choice for sorting large arrays and linked lists.

Although it uses extra space, its stability and consistent performance give it an edge over some other algorithms.

FAQ's related to Merge Sort in Java

1. What is the idea behind merge sort?

Answer:

Merge Sort is based on the divide and conquer technique. It splits the array into halves, recursively sorts them, and merges the sorted halves to produce the final sorted array.

2. Is merge sort in place sorting algorithm?

Answer:

No, Merge Sort is not in-place. It uses extra space for temporary arrays during the merge process, which leads to a space complexity of O(n).

3. Why is merge sort a stable sorting algorithm?

Answer:

Merge Sort maintains the relative order of equal elements while merging, which makes it stable. This is important when sorting records with multiple fields (like name and age).

4. What is the time complexity of Merge Sort in all cases?

Answer:

Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases, making it very predictable and efficient even for large datasets.

5. Why is merge sort preferred over quick sort?

Answer:

Merge Sort is preferred when stability is required or when dealing with linked lists. It is also a better choice in worst case scenarios where Quick Sort can degrade to O(n²).

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

Unlock this article for Free,
by logging in

Merge Sort in Java