Recursive Merge Sort Implementation in Java

Introduction

Merge Sort is an efficient and stable sorting algorithm that uses the Divide and Conquer Technique for sorting an array. In this lab, you will be learning how to implement Merge Sort in Java using a recursive approach.

Skills Graph

Create a Merge Sort method

Create a public static method named mergeSort() with three integer parameters, int arrToSort[], startIdx, endIdx. You need to check if the array length is less than 2, then return. Otherwise, calculate the middle index of the array and split the array into the left and right halves. The left and right halves should be recursively divided too. After dividing them, you have to merge them together to form a sorted array.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

Create a Merge method

Create another public static method named merge() with four parameters: int arrToSort[], startIdx, midIdx, and endIdx. You need to initialize the left and right arrays. Then, you need to merge both arrays by comparing the elements of each array and merging them into a single array.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

Test Merge Sort

Let's test the mergeSort() method by writing code to sort an input array. Create a main method. Then, declare an integer array with a few unsorted values. Call the mergeSort() method and pass the unsorted array to it. Finally, print the sorted array to the console. The code block for this step will look like this:

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

After running the program, the output should be: [0, 1, 2, 4, 6, 8].

Test with Empty Array

Create another test for an empty array. Declare an empty integer array. Call the mergeSort() method and pass it to the empty array. Finally, print the sorted array to the console. The code block for this step will look like this:

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

The output should be same as input.

Test with Single Element Array

Create one more test with a single element array. Declare a single-element integer array. Call the mergeSort() method and pass it to the single-element array. Finally, print the sorted array to the console. The code block for this step will look like this:

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

The output should be same as input.

Test with Negative Values

Create another test for an array consisting of negative integers. Declare an integer array that includes some negative integers. Call the mergeSort() method and pass the array as an argument. Finally, print the sorted array to the console. The code block for this step will look like this:

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

After running the program, the output should be: [-9, -7, -1, 0, 2, 6, 8].

Test with Non-numeric Elements

Create another test by sorting an array of non-numerical elements. Declare an array of strings. Call the mergeSort() method and pass the array as an argument. Finally, print the sorted array to the console. The code block for this step will look like this:

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

After running the program, the output should be: ['Bob', 'Christine', 'David', 'Emily', 'John'].

Final source code

Here is the final source code for Merge Sort:

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //create an unsorted integer array
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //sort the integer array using Merge Sort
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrToSort));

       //create an empty integer array
       int[] emptyArr = {};
       //sort the empty array
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(emptyArr));

       //create a single-element array
       int[] singleElementArr = {7};
       //sort the single-element array
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(singleElementArr));

       //create a negative integer array
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //sort the negative integer array
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrWithNegatives));

       //create a string array
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //sort the string array
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(strsToSort));
   }
}

Run the program

Compile and run the program using the terminal:

javac MergeSort.java && java MergeSort

Summary

In this lab, you learned what is Merge Sort, how it works and how to implement it in Java. You created two public static methods, mergeSort() and merge() to divide and merge the input array respectively. After the implementation, you tested it on various inputs, discussed the time and space complexity, and verified its functionality. Congratulations! You have successfully completed the Merge Sort lab in Java.