How to merge two sorted subarrays in the Merge Sort algorithm in Java

Introduction

This tutorial will guide you through the process of merging two sorted subarrays in the Merge Sort algorithm using the Java programming language. Merge Sort is a popular and efficient divide-and-conquer algorithm used for sorting large datasets. Understanding the merging process is crucial for implementing the Merge Sort algorithm effectively in Java applications.

Understanding Merge Sort Algorithm

Merge Sort is a popular and efficient sorting algorithm that follows the divide-and-conquer paradigm. It works by recursively dividing the input array into smaller subarrays, sorting them, and then merging the sorted subarrays back together to form the final sorted array.

The key steps of the Merge Sort algorithm are:

Divide

1. Divide the input array into two halves until you have single-element subarrays.

Conquer

2. Sort the individual subarrays by comparing their elements and merging them.

Combine

3. Merge the sorted subarrays back together to form the final sorted array.

The time complexity of Merge Sort is O(n log n), making it an efficient choice for sorting large datasets. It is particularly useful in scenarios where the input array is too large to fit in memory, as it can be efficiently implemented using external storage or distributed computing.

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }
}

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

The above code demonstrates the implementation of the Merge Sort algorithm in Java. The mergeSort method recursively divides the input array into smaller subarrays, and the merge method combines the sorted subarrays back together to form the final sorted array.

Merging Sorted Subarrays in Merge Sort

The key step in the Merge Sort algorithm is the merging of the sorted subarrays. This process involves combining two or more sorted subarrays into a single sorted array.

Merge Operation

The merge operation is performed by comparing the elements of the sorted subarrays and placing them in the correct order in the final array. The general steps are:

1. Initialize three pointers: one for the left subarray, one for the right subarray, and one for the merged array.
2. Compare the elements at the current positions of the left and right subarrays.
3. Add the smaller element to the merged array and move the corresponding pointer forward.
4. Repeat step 2 and 3 until one of the subarrays is exhausted.
5. Add the remaining elements from the non-empty subarray to the merged array.

Here's an example implementation of the merge operation in Java:

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

This implementation merges the two sorted subarrays left and right into the original array arr.

Visualization of Merge Operation

The merge operation can be visualized using a diagram like the one below:

graph TD
    A[Left Subarray] --> B[Merged Array]
    C[Right Subarray] --> B
    B --> D[Sorted Array]

In this diagram, the left and right subarrays are merged into the final sorted array.

By understanding the merge operation, you can effectively implement the Merge Sort algorithm and sort arrays efficiently in Java.

Implementing Merge Sort in Java

Now that we have a solid understanding of the Merge Sort algorithm and the merge operation, let's dive into the implementation of Merge Sort in Java.

Merge Sort Algorithm Implementation

The Merge Sort algorithm can be implemented in Java using the following steps:

1. Define a mergeSort method that takes an input array.
2. If the array has more than one element, divide it into two halves.
3. Recursively call the mergeSort method on the left and right halves.
4. Merge the sorted left and right halves using the merge method.

Here's the Java code that implements the Merge Sort algorithm:

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }
}

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

Let's break down the code:

1. The mergeSort method takes an input array arr.
2. If the array has more than one element, it is divided into two halves using the mid variable.
3. The left and right subarrays are created using Arrays.copyOfRange.
4. The mergeSort method is recursively called on the left and right subarrays.
5. The merge method is called to combine the sorted left and right subarrays back into the original arr.

The merge method is responsible for merging the two sorted subarrays by comparing their elements and placing them in the correct order in the final array.

Time Complexity

The time complexity of the Merge Sort algorithm is O(n log n), which makes it an efficient choice for sorting large datasets. The divide-and-conquer approach used in Merge Sort ensures that the algorithm scales well with the size of the input.

By understanding the implementation of Merge Sort in Java, you can effectively use this algorithm to sort arrays and solve various sorting-related problems.

Summary

In this Java tutorial, you have learned how to efficiently merge two sorted subarrays in the Merge Sort algorithm. By understanding the step-by-step process and implementing the merge operation in Java, you can effectively apply the Merge Sort algorithm to sort large datasets and improve the performance of your Java applications.