Merge Sort in Java: A Complete Step-by-Step Guide with Code & Explanation

Sorting is a fundamental operation in computer science, and Merge Sort is one of the most efficient algorithms available. It is widely used in applications where stable and efficient sorting is required.

In this article, we will cover:

? What is Merge Sort?

? Step-by-step breakdown using an example

? Java implementation of Merge Sort

? Time and space complexity analysis

? When to use Merge Sort

By the end of this article, you will fully understand Merge Sort and be able to implement it in Java!

1?? What is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm that works by:

1. Dividing the array into two halves.
2. Recursively sorting each half.
3. Merging the sorted halves back together.

Why Use Merge Sort?

? Always O(n log n) time complexity

? Stable sorting algorithm (Preserves order of equal elements)

? Efficient for linked lists and large datasets

2?? Step-by-Step Merge Sort Example

Let’s sort the initial array:

[8, 5, 9, 1, 6, 7]        

?? Step 1: Divide the Array

The array is repeatedly split into two halves: (find the median = (left index + right index/2))

[8, 5, 9]   and   [1, 6, 7]        

Each half is further divided:

[8, 5]   [9]   and   [1, 6]   [7]        

Breaking it down further:

[8]   [5]   [9]   [1]   [6]   [7]        

At this point, each element is a single unit, which means it is trivially sorted.

?? Step 2: Merge the Sorted Halves

Now, we merge the elements back together in sorted order.

Merging [8] and [5]

[5, 8]        

Merging [1] and [6]

[1, 6]        

Now, merge [5, 8] and [9]:

[5, 8, 9]        

Merge [1, 6] and [7]:

[1, 6, 7]        

Finally, merge [5, 8, 9] and [1, 6, 7]:

? Final Sorted Array: [1, 5, 6, 7, 8, 9]

3?? Java Implementation of Merge Sort

Now, let's implement Merge Sort in Java:

import java.util.Arrays;

public class MergeSort {

    public static void mergeSort(int arr[], int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int arr[], int left, int mid, int right) {
        int leftSize = mid - left + 1;
        int rightSize = right - mid;
        
        int leftArray[] = new int[leftSize];
        int rightArray[] = new int[rightSize];

        for (int i = 0; i < leftSize; i++)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < rightSize; j++)
            rightArray[j] = arr[mid + 1 + j];

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

        while (i < leftSize) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < rightSize) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String args[]) {
        int arr[] = {8, 5, 9, 1, 6, 7};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}        

? How does this work?

1?? Recursively divide the array into smaller subarrays.

2?? Sort individual parts.

3?? Merge two sorted halves into one sorted array.

?? Best case: O(n log n) in all cases.

4?? Time & Space Complexity Analysis

?? Space Complexity:

• O(n) due to extra arrays used in merging.

5?? When Should You Use Merge Sort?

?? Use Cases:

? Sorting Linked Lists (No need for extra space)

? Sorting Large Datasets on Disk (External Sorting)

? Stable Sorting (Preserves Order of Equal Elements)

?? Avoid for:

? In-Place Sorting Needs (Merge Sort Uses Extra Memory)

? Small Arrays (Insertion Sort Might Be Better)

6?? Comparing Merge Sort with Other Sorting Algorithms

?? Key Insights:

• Merge Sort is always O(n log n), unlike Quick Sort (which can be O(n2)).
• Quick Sort is faster in practice for in-memory sorting due to lower space overhead.
• Merge Sort is preferred for linked lists and external sorting.

?? Merge Sort Summary:

• O(n log n) time complexity in all cases.
• Stable sorting algorithm.
• Uses extra space but provides consistent performance.
• Best suited for linked lists and external sorting applications.

?? Have you ever implemented Merge Sort? What’s your favorite sorting algorithm? Let’s discuss!