Skip to main content

Computational Problem Solving with Java and Interactive Object Graphics

Mark F. Russo, PhD

Section 13.6 Merge Sort

The merge sort algorithm is a popular and efficient divide-and-conquer sorting algorithm that works by breaking down a collection or array into smaller subsequences, sorting those sublists, and then merging them back together to create a fully sorted sequence. It’s known for its stable sorting behavior and its guaranteed worst-case time complexity of \(O(N logN)\text{,}\) making it suitable for sorting large datasets.
The merge sort algorithm works as follows.
  1. Input: The algorithm takes an unsorted collection or array of elements as input.
  2. Divide Phase: Divide the sequence into two halves, roughly equal in size. This is the recursive step of the algorithm.
  3. Recursion: Recursively apply the merge sort algorithm to each of the two halves. This involves breaking down the sublists further until they become small enough to be considered sorted (typically lists of size 1).
  4. Merge Phase: Merge the sorted sublists back together to create a larger sorted sublist. This involves comparing elements from the two sublists and placing them in order in the merged sequence.
  5. Repeat Merge: Continue merging the sublists until you have a single sorted sequence that contains all the elements.
  6. Termination: Once all sublists are merged and sorted, the entire sequence is sorted in ascending order.
The key to the efficiency of the merge sort algorithm lies in the merging step. Merging two sorted sublists into a single sorted sequence takes linear time \(O(N)\text{,}\) where \(N\) is the total number of elements in the sequence. Because the sequence is divided in half at each recursive step, the depth of the recursion is \(log_2(N)\text{,}\) and at each level, the merging step takes linear time. Thus, the overall time complexity of merge sort is \(O(N logN)\text{.}\)
Merge sort’s efficiency, stability, and predictable worst-case behavior make it a popular choice for sorting tasks, especially when dealing with large datasets. However, it does require additional memory space for creating temporary subsequences during the merging process. This space complexity might be a consideration when working with limited memory resources.
In Listing 13.6.1 the mergeSort(…) function takes an array (arr), a left index (left), and a right index (right) as parameters and sorts the array using the merge sort algorithm. The merge function is responsible for merging two sorted subarrays. The main method demonstrates how to use the merge sort function on an array.
The merge sort algorithm divides the array into two halves, sorts each half, and then merges them back together while maintaining the sorted order. After sorting, the output will display the original array and the sorted array.
// MergeSort.java
import java.util.Arrays;

public class MergeSort {

  // Merge function to merge two subarrays
  static void merge(int[] arr, int left, int mid, int right) {
    int N1 = mid - left + 1;
    int N2 = right - mid;

    int[] leftArray  = new int[N1];
    int[] rightArray = new int[N2];

    // Copy data to temporary 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];
    }

    int i = 0, j = 0, k = left;

    // Merge the two arrays back into the original array
    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 from leftArray, if any
    while (i < N1) {
      arr[k] = leftArray[i];
      i++;
      k++;
    }

    // Copy remaining elements from rightArray, if any
    while (j < N2) {
      arr[k] = rightArray[j];
      j++;
      k++;
    }
  }

  // Merge sort function
  static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
      int mid = left + (right - left) / 2;

      // Sort the first and second halves
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);

      // Merge the sorted halves
      merge(arr, left, mid, right);
    }
  }

  public static void main(String[] args) {
    int[] arrayToSort = { 12, 11, 13, 5, 6, 7 };
      
    System.out.println("Original array: " + Arrays.toString(arrayToSort));
    mergeSort(arrayToSort, 0, arrayToSort.length - 1);  
    System.out.println("Sorted array: " + Arrays.toString(arrayToSort));
  }
}
Listing 13.6.1. 
javac MergeSort.java
java MergeSort
Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]
<Prev^TopNext>