Implementation of Merge Sort in Java Programming Language

Merge Sort is one of the most efficient and widely used sorting algorithms. It follows the divide-and-conquer approach, which means it breaks down a problem into smaller subproblems, solves them, and then combines the results. Merge Sort is particularly useful because it guarantees a time complexity of O(n log n) in all cases, making it a reliable choice for sorting large datasets.

In this article, we will briefly touch upon how Merge Sort works, go through its implementation in Java and understand the implementation.

How Merge Sort Works

Merge Sort works by recursively dividing the input array into smaller subarrays until each subarray contains only one element. Then, it keeps merging these subarrays in a sorted order. Here’s a step-by-step breakdown:

Divide: Split the array into two halves.
Conquer: Recursively sort each half.
Combine: Merge the two sorted halves into a single sorted array.

Refer to these articles for better understanding on how merge sort algorithm works:

Implementation of Merge Sort Algorithm in Java

Here’s the implementation of Merge Sort Algorithm in Java:


import java.util.Arrays;

public class MergeSort {
  public static void mergeSort(int[] arr, int left, int right) {
    /**
     * Recursively sorts the array using the merge sort algorithm.
     *
     * @param arr   The array to be sorted.
     * @param left  The starting index of the array segment to be sorted.
     * @param right The ending index of the array segment to be sorted.
     */
    if (left < right) {
      // Find the middle point to divide the array into two halves
      int mid = (left + right) / 2;
      
      // Recursively sort the left half of the array
      mergeSort(arr, left, mid);
      
      // Recursively sort the right half of the array
      mergeSort(arr, mid + 1, right);
      
      // Merge the two sorted halves
      merge(arr, left, mid, right);
    }
  }

  private static void merge(int[] arr, int left, int mid, int right) {
    /**
     * Merges two sorted subarrays into a single sorted array.
     *
     * @param arr   The array containing the two subarrays to be merged.
     * @param left  The starting index of the first subarray.
     * @param mid   The ending index of the first subarray.
     * @param right The ending index of the second subarray.
     */
    // Calculate the sizes of the two subarrays
    int n1 = mid - left + 1;  // Size of the left subarray
    int n2 = right - mid;     // Size of the right subarray

    // Create temporary arrays to hold the two subarrays
    int[] L = new int[n1];
    int[] R = new int[n2];

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

    // Initialize indices for the subarrays and the main array
    int i = 0;  // Index for the left subarray (L)
    int j = 0;  // Index for the right subarray (R)
    int k = left;  // Index for the main array (arr)

    // Merge the two subarrays back into the main array
    while (i < n1 && j < n2) {
      if (L[i] <= R[j]) {
        // If the current element in L is smaller, add it to the main array
        arr[k] = L[i];
        i++;
      } else {
        // If the current element in R is smaller, add it to the main array
        arr[k] = R[j];
        j++;
      }
      k++;
    }

    // Copy any remaining elements from the left subarray (if any)
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

    // Copy any remaining elements from the right subarray (if any)
    while (j < n2) {
      arr[k] = R[j];
      j++;
      k++;
    }
  }

  // Example usage
  public static void main(String[] args) {
    // Define the array to be sorted
    int[] arr = {4, 1, 2, 3};
    
    // Print the original array
    System.out.println("Original array: " + Arrays.toString(arr));
    
    // Call the mergeSort function to sort the array
    mergeSort(arr, 0, arr.length - 1);
    
    // Print the sorted array
    System.out.println("Sorted array: " + Arrays.toString(arr));
  }
}

Explanation of the Implementation

Let’s break down the merge sort implementation step by step to understand how it works.

The `mergeSort` Method

The mergeSort method is the main method that performs the sorting. It takes three parameters:

arr: The array to be sorted.
left: The starting index of the segment of the array to be sorted.
right: The ending index of the segment of the array to be sorted.

Here’s how it works:

Base Condition: The method first checks if left < right. This condition ensures that the array has more than one element. If left is not less than right, it means the array has either one or zero elements, and no sorting is needed.
Divide the Array: If the array has more than one element, the method calculates the middle index (mid) using the formula (left + right) / 2. This divides the array into two halves.
Recursive Calls: The method then calls itself recursively to sort the left half (mergeSort(arr, left, mid)) and the right half (mergeSort(arr, mid + 1, right)). This process continues until the array is divided into single-element subarrays.
Merge the Sorted Halves: Once the two halves are sorted, the merge method is called to merge them back into a single sorted array.

The `merge` Method

The merge method is responsible for merging two sorted subarrays into a single sorted array. It takes four parameters:

arr: The array containing the two subarrays to be merged.
left: The starting index of the first subarray.
mid: The ending index of the first subarray.
right: The ending index of the second subarray.

Here’s how it works:

Calculate Subarray Sizes: The sizes of the two subarrays are calculated using n1 = mid - left + 1 (size of the left subarray) and n2 = right - mid (size of the right subarray).
Create Temporary Arrays: Two temporary arrays, L and R, are created to hold the elements of the left and right subarrays. The elements are copied from the main array to these temporary arrays.
Merge Process: The method then merges the two subarrays back into the main array (arr). It uses three indices:
- i: Index for the left subarray (L).
- j: Index for the right subarray (R).
- k: Index for the main array (arr).
The method compares the elements of L and R one by one. The smaller element is placed into the main array, and the corresponding index (i or j) is incremented. This process continues until all elements from either L or R are placed into the main array.
Copy Remaining Elements: If there are any remaining elements in L or R, they are copied directly into the main array.

Example Run

Let’s walk through an example with the array [4, 1, 2, 3]:

The mergeSort method is called with left = 0 and right = 3.
The array is divided into two halves: [4, 1] and [2, 3].
Each half is further divided and sorted recursively:
- [4, 1] becomes [4] and [1], which are merged into [1, 4].
- [2, 3] becomes [2] and [3], which are merged into [2, 3].
Finally, the two sorted halves [1, 4] and [2, 3] are merged into the final sorted array [1, 2, 3, 4].