Merge Sort in Java

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:

  1. Divide: Split the array into two halves recursively.
  2. Conquer: Sort each half recursively.
  3. 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)
Merge Sort in Java
Merge Sort in Java

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:

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

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:

  1. 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.
  2. 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.

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.

Merge sort in Java Meme

FAQ's related to Merge Sort in Java

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.

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).

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).

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.

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription