How To Do Merge Sort in Java

Introduction

Merge Sort is a classic and highly efficient sorting algorithm based on the divide and conquer paradigm. It splits an array into smaller subarrays, recursively sorts those subarrays, and then merges them back together in a sorted manner. Merge Sort guarantees a time complexity of O(n log n) even in the worst-case scenario, making it one of the most reliable and predictable sorting algorithms.

In this blog post, we’ll explore how Merge Sort works, break down its implementation in Java, and compare its performance to other common sorting algorithms like Quick Sort and Bubble Sort.

What Is Merge Sort?

Merge Sort was developed to efficiently sort large datasets. It splits the input array into two halves, sorts each half, and then merges the two sorted halves into a single sorted array. This process continues recursively until the array is fully sorted. It’s handy when stability (i.e., preserving the order of equal elements) is important or when working with large datasets.

Merge Sort is known for its consistent time complexity of O(n log n) across best, average, and worst cases, making it superior to other algorithms like Quick Sort regarding worst-case performance.

Here’s a fleshed-out blog post on Merge Sort in Java, following a similar structure to the TimSort example:

How Merge Sort Works

The Merge Sort algorithm involves three main steps:

1. Divide: Recursively split the input array into two halves until each subarray has one element.
2. Conquer: Recursively sort the two halves by dividing them further.
3. Combine: Merge the sorted halves back together to form the final sorted array.

Key Concepts:

• Divide and Conquer: The array is recursively divided into smaller subarrays, which are then sorted and merged.
• Merging: During the merge step, two sorted subarrays are combined into one sorted array by comparing elements and inserting them in the correct order.

To see how Merge Sort works, visit our free Sorting Algorithm Visualizer.

Pseudocode for Merge Sort

MergeSort(arr[], l, r):
    if l < r:
        1. Find the middle point m = l + (r - l) / 2
        2. Recursively sort the first half: MergeSort(arr, l, m)
        3. Recursively sort the second half: MergeSort(arr, m + 1, r)
        4. Merge the two halves: merge(arr, l, m, r)

merge(arr[], l, m, r):
    1. Create temporary arrays L[] and R[]
    2. Copy data to temporary arrays L[] and R[]
    3. Merge the temporary arrays back into arr[l..r]
    4. Copy any remaining elements of L[] and R[] to arr[]

Java Implementation of Merge Sort

Here’s the complete Java implementation of Merge Sort:

public class MergeSort {

    // Main function that sorts arr[l..r] using merge()
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = l + (r - l) / 2;

            // Sort first and second halves
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    // Merge two halves function
    public static void merge(int[] arr, int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        // Create temp arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        // Merge the temp arrays
        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

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

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

    // Helper function to print the array
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // Main method
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10, 39, 44, 73};
        System.out.println("Given Array:");
        printArray(arr);

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

        System.out.println("\nSorted Array:");
        printArray(arr);
    }
}

Step-by-Step Example: How Merge Sort Works on a Large Array

To understand how Merge Sort operates, let’s walk through a step-by-step example using the array:

Array: [38, 27, 43, 3, 9, 82, 10, 39, 44, 73]

Step 1: Dividing the Array

The array is recursively divided in half until each subarray contains one element:

Initial Array: [38, 27, 43, 3, 9, 82, 10, 39, 44, 73]
Split into two halves:
Left: [38, 27, 43, 3, 9]
Right: [82, 10, 39, 44, 73]

Keep dividing until each subarray contains one element:

Left: [38, 27, 43, 3, 9]
      -> [38, 27] -> [38], [27]
      -> [43]
      -> [3, 9] -> [3], [9]

Right: [82, 10, 39, 44, 73]
      -> [82, 10] -> [82], [10]
      -> [39]
      -> [44, 73] -> [44], [73]

Step 2: Merging the Halves

Now, we merge the single-element arrays in sorted order:

• Merge [38] and [27] → [27, 38]
• Merge [3] and [9] → [3, 9]
• Merge [82] and [10] → [10, 82]
• Merge [44] and [73] → [44, 73]

At this point, the array looks like:

Left: [27, 38], [43], [3, 9]
Right: [10, 82], [39], [44, 73]

Next, we merge the sorted subarrays:

• Merge [27, 38] and [43] → [27, 38, 43]
• Merge [3, 9] with [27, 38, 43] → [3, 9, 27, 38, 43]
• Merge [10, 82] and [39] → [10, 39, 82]
• Merge [10, 39, 82] with [44, 73] → [10, 39, 44, 73, 82]

Finally, merge the two halves:

• Merge [3, 9, 27, 38, 43] with [10, 39, 44, 73, 82] → [3, 9, 10, 27, 38, 39, 43, 44, 73, 82]

Final Sorted Array:

[3, 9, 10, 27, 38, 39, 43, 44, 73, 82]

Performance Test: Merge Sort vs Quick Sort vs Bubble Sort

Now that we’ve reviewed how Merge Sort works, let’s compare its performance to other standard algorithms: Quick Sort and Bubble Sort. We’ll test the algorithms on random, sorted, reverse-sorted, and partially sorted arrays.

Here’s the benchmarking code in Java, including partially sorted arrays:

import java.util.Arrays;
import java.util.Random;

public class SortingBenchmark {

    public static void main(String[] args) {
        // Define the array sizes to test
        int[] sizes = {1000, 5000, 10000};
        Random random = new Random();

        // Loop through each array size
        for (int size : sizes) {
            // Generate random arrays of the given size
            int[] randomArray = random.ints(size, 0, 10000).toArray();  // Random array
            int[] sortedArray = Arrays.copyOf(randomArray, randomArray.length);  // Sorted array
            Arrays.sort(sortedArray);  // Sort the array to make it "Sorted"
            int[] reverseArray = Arrays.copyOf(sortedArray, sortedArray.length);  // Reverse-sorted array
            reverseArray(reverseArray);  // Reverse the sorted array
            int[] partiallySortedArray = generatePartiallySortedArray(size);  // Partially sorted array

            System.out.println("\nArray size: " + size);

            // Test Merge Sort
            System.out.println("Merge Sort:");
            benchmark("Random", randomArray, () -> mergeSort(randomArray));
            benchmark("Sorted", sortedArray, () -> mergeSort(sortedArray));
            benchmark("Reverse", reverseArray, () -> mergeSort(reverseArray));
            benchmark("Partially Sorted", partiallySortedArray, () -> mergeSort(partiallySortedArray));

            // Test Quick Sort
            System.out.println("Quick Sort:");
            benchmark("Random", randomArray, () -> quickSort(randomArray));
            benchmark("Sorted", sortedArray, () -> quickSort(sortedArray));
            benchmark("Reverse", reverseArray, () -> quickSort(reverseArray));
            benchmark("Partially Sorted", partiallySortedArray, () -> quickSort(partiallySortedArray));

            // Test Bubble Sort (for comparison)
            System.out.println("Bubble Sort:");
            benchmark("Random", randomArray, () -> bubbleSort(randomArray));
            benchmark("Sorted", sortedArray, () -> bubbleSort(sortedArray));
            benchmark("Reverse", reverseArray, () -> bubbleSort(reverseArray));
            benchmark("Partially Sorted", partiallySortedArray, () -> bubbleSort(partiallySortedArray));
        }
    }

    // Reverse an array (used to create reverse sorted array)
    public static void reverseArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[n - i - 1];
            arr[n - i - 1] = temp;
        }
    }

    // Generate a partially sorted array where half the array is sorted
    public static int[] generatePartiallySortedArray(int size) {
        Random random = new Random();
        int[] arr = random.ints(size, 0, 10000).toArray();
        Arrays.sort(arr, 0, size / 2);  // Sort only the first half of the array
        return arr;
    }

    // Benchmarking method to measure and print the time taken by each sorting algorithm
    public static void benchmark(String arrayType, int[] arr, Runnable sortingAlgorithm) {
        int[] arrCopy = Arrays.copyOf(arr, arr.length);  // Create a copy to avoid modifying the original array
        long startTime = System.nanoTime();  // Start the timer
        sortingAlgorithm.run();  // Run the sorting algorithm
        long endTime = System.nanoTime();  // End the timer
        System.out.println(arrayType + ": " + (endTime - startTime) / 1e6 + " ms");  // Print the time taken in milliseconds
    }

    // Merge Sort: Initialize recursive merge sort call
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);  // Call the recursive merge sort with start and end indices
    }

    // Recursive Merge Sort function
    public static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = l + (r - l) / 2;

            // Recursively sort both halves
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    // Merge function to combine two sorted subarrays into one
    public static void merge(int[] arr, int l, int m, int r) {
        // Sizes of two subarrays
        int n1 = m - l + 1;
        int n2 = r - m;

        // Temporary arrays for the two subarrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data into temporary arrays
        for (int i = 0; i < n1; ++i) L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j];

        // Initial indexes of the two subarrays
        int i = 0, j = 0, k = l;

        // Merge the two sorted subarrays back into arr[]
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

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

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

    // Quick Sort: Initialize recursive quick sort call
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);  // Call the recursive quick sort with start and end indices
    }

    // Recursive Quick Sort function
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after the partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    // Partition function for Quick Sort
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // Set the pivot element
        int i = low - 1;  // Index of the smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to the pivot, swap it
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        // Swap the pivot element with the element at the correct position
        swap(arr, i + 1, high);
        return i + 1;
    }

    // Helper function to swap two elements in the array
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Bubble Sort function
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                // Swap if the current element is greater than the next element
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
}

Results

Performance of Merge Sort, Quick Sort, and Bubble Sort

Array Size & Configuration	Merge Sort (ms)	Quick Sort (ms)	Bubble Sort (ms)
1000 (Random)	1.390	0.530	6.841
1000 (Sorted)	0.142	2.922	2.838
1000 (Reverse)	0.121	3.829	1.257
1000 (Partially Sorted)	0.147	0.223	1.443
5000 (Random)	0.906	0.947	36.880
5000 (Sorted)	0.855	36.624	6.701
5000 (Reverse)	0.911	15.085	20.397
5000 (Partially Sorted)	0.884	0.539	23.167
10000 (Random)	1.964	1.132	147.377
10000 (Sorted)	1.072	47.479	20.824
10000 (Reverse)	1.334	53.569	74.993
10000 (Partially Sorted)	1.657	0.838	108.824

Note: Times are rounded to three decimal places for readability. Actual performance may vary slightly due to system-specific factors.

Key Takeaways

1. Merge Sort and Quick Sort are consistently faster than Bubble Sort:
   • Across all test cases and array sizes, Merge Sort and Quick Sort outperform Bubble Sort, especially for large arrays. Bubble Sort‘s O(n²) time complexity results in very slow performance as the array size increases.
   • For example, with 10,000 random elements, Merge Sort took 1.964 ms, Quick Sort took 1.132 ms, and Bubble Sort took 147.377 ms.
2. Quick Sort struggles with sorted and reverse-sorted arrays:
   • Quick Sort‘s performance significantly degrades on sorted and reverse-sorted arrays due to its basic pivot selection strategy (the last element is the pivot). It suffers from worst-case O(n²) performance in these cases.
   • For example, on a 10000 reverse-sorted array, Quick Sort took 53.569 ms, while Merge Sort remained efficient at 1.334 ms.
3. Merge Sort’s stable performance:
   • Merge Sort consistently performs well across all configurations (random, sorted, reverse-sorted, and partially sorted). Its O(n log n) time complexity allows it to handle both small and large arrays efficiently.
   • Merge Sort’s best performance was 0.121 ms for 1000 reverse-sorted elements and 0.147 ms for 1000 partially sorted elements.
4. Bubble Sort is inefficient for large arrays:
   • Bubble Sort‘s performance drops dramatically as the array size increases. For example, on a 10000 random array, Bubble Sort took 147.377 ms, making it unsuitable for large datasets.
5. Quick Sort excels with partially sorted arrays:
   • Quick Sort performs exceptionally well with partially sorted arrays, showing faster times than Merge Sort and Bubble Sort in these cases.
   • For example, with 10,000 partially sorted elements, Quick Sort took just 0.838 ms, faster than Merge Sort, which took 1.657 ms.

Summary

• Merge Sort is a reliable and consistent algorithm across all test cases, making it an excellent choice for scenarios where array order isn’t known beforehand.
• Quick Sort is generally fast but can struggle with sorted or reverse-sorted arrays due to poor pivot selection. It excels with partially sorted arrays.
• Bubble Sort should be avoided for large arrays due to its poor scalability, though it performs decently on small or mostly sorted arrays.

Pros and Cons of Merge Sort

Pros:

• Guaranteed O(n log n) Time Complexity: Merge Sort performs consistently, even in the worst-case scenario.
• Stable Sorting: It preserves the relative order of elements with equal values.
• Best for Large Datasets: Its predictable time complexity makes it ideal for sorting large datasets.

Cons:

• Space Complexity: Merge Sort requires extra space for the temporary arrays used during merging.
• Recursion Overhead: The recursive nature of Merge Sort adds overhead, particularly for small arrays.

When to Use Merge Sort

• Stability is Required: Use Merge Sort when stability is important, i.e., when the order of equal elements should be preserved.
• Sorting Large Datasets: Merge Sort is particularly well-suited for large datasets because of its predictable O(n log n) performance.
• Performance in the Worst Case: If you expect worst-case inputs like already sorted or reverse-sorted arrays, Merge Sort performs more consistently than Quick Sort.

Conclusion

Merge Sort’s predictable performance across various arrays makes it an excellent choice for large datasets or scenarios where worst-case performance is a concern. Its efficiency with sorted and reverse-sorted arrays and consistent O(n log n) time complexity outshine Quick Sort’s vulnerability to poor pivot selection in such cases. Merge Sort outperforms Bubble Sort in all configurations and is more reliable than Quick Sort when dealing with reverse-sorted or partially sorted arrays. While Quick Sort may have better average-case performance on random arrays, Merge Sort’s stability, guaranteed worst-case performance, and memory efficiency make it a highly reliable choice for handling diverse datasets.

Congratulations on reading to the end of this tutorial!

To implement Merge Sort in C++, go to the article How To Do Merge Sort in C++.

To implement Merge Sort in Rust, go to the article How To Do Merge Sort in Rust.

Have fun and happy researching!