Merge Sort with Java

The merge sort is a sorting algorithm that uses a divide-and-conquer strategy to sort an array of elements. It is an efficient sorting algorithm, with an average time complexity of O(n log n).

The merge sort algorithm works by recursively dividing the input array into two halves until each half contains only one element or is empty. Then, it merges the sorted subarrays back together to produce the final sorted array.

The merge step involves comparing the first element of each subarray and selecting the smaller one to be placed into the final array. This process continues until all elements have been merged into the final sorted array.

One of the advantages of merge sort is that it is a stable sorting algorithm, meaning that elements with the same value will retain their original order in the sorted array. Additionally, merge sort can be easily implemented in a parallelized manner, making it a popular choice for large-scale sorting applications.

Let’s see a diagram from the Merge sort to have an idea of how it works and also what is the order of execution:

Red Element Squares: The elements are still being divided and not sorted yet.
Grey Element Squares: There is only one element, therefore, the array is fully divided.
Green Element Squares: The merge starts being done and also the sorting of all elements.

The number beneath each element represents the order of execution in the algorithm. If we debug the code, we will see that the execution order will be exactly the same.

Merge Sort Code with Java

The following code makes use of recursion and if you are not familiar with it, I highly recommend you to read the following article, Mastering Programming Recursion with Java.

Now, notice in the following code that the left and right arrays will be divided, then they will be merged and finally merged. Read the code carefully, this is not an easy algorithm to grasp, therefore, you might have to read it many times to fully absorb it.

Another thing that will help you is to debug this algorithm to see in practice the process described in the above diagram.

public class MergeSort {

    public static void main(String[] args) {
        var array = new int[] {3, 9, 10, 1, 8, 7, 5, 2};
        mergeSort(array);
        for (int element: array) {
            System.out.print(element + " ");
        }
    }

    public static void mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        // Break the array in two halves
        int mid = array.length / 2;
        int[] leftArray = new int[mid];
        int[] rightArray = new int[array.length - mid];

        System.arraycopy(array, 0, leftArray, 0, mid);

        if (array.length - mid >= 0)
            System.arraycopy(array, mid, rightArray, 
                              0, array.length - mid);

        mergeSort(leftArray);
        mergeSort(rightArray);
        merge(leftArray, rightArray, array);
    }

    private static void merge(int[] leftArray, 
                              int[] rightArray, int[] array) {
        int i = 0, j = 0, k = 0;

        // Effectively sorts left and right array
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                array[k++] = leftArray[i++];
            } else {
                array[k++] = rightArray[j++];
            }
        }
        while (i < leftArray.length) {
            array[k++] = leftArray[i++];
        }
        while (j < rightArray.length) {
            array[k++] = rightArray[j++];
        }
    }
}

Output:
1 2 3 5 7 8 9 10

Code analysis:

As you can see in the above code, the first step is to invoke the mergeSort method. Within this method, we can see the base condition from the recursion which is whenever the array reaches the size of 0 or 1.

Until the recursion doesn’t reach the base condition, the dividing process in the array will continue. When the recursion reaches the base condition from the merge sort, then the sorting will start and the elements will also be merged.

The left side of the array will be sorted before the right array. When both sides are divided, merged, and sorted the final left and right sides will be merged and the whole array will be sorted.

When to Use Merge Sort?

The merge sort algorithm is a good choice in the following scenarios when:

Stability is important: Merge sort is a stable sorting algorithm. This means that it does not change the order of elements that are the same. This is important if there is some special configuration within each element such as a timestamp metadata. Therefore, if we have an array as the following { 3, 2, 2, 2, 1}, the elements with the value of 2 won’t change the order. On the other hand, sorting algorithms such as Quicksort or Heapsort will perform unstable sorting meaning that elements with the same value will change their order.

Space is not a constraint: Merge sort requires additional space proportional to the size of the input array. It needs space for the temporary arrays used during the merge process. Merge sort doesn’t sort the array in place, this means, it doesn’t use the same input array.

The input array is large: Merge sort performs better than other O(n log n) algorithms like Quicksort for larger arrays. This is because merge sort does fewer comparisons than Quicksort in practice.

The input array is partially sorted: Merge sort performs well for partially sorted arrays. It does not do unnecessary swapping of elements like quicksort. It simply merges the sorted parts efficiently.

In short, use merge sort when:

• Stability is important
• Space is not an issue
• Input size is large
• Input is partially sorted

When to NOT Use Merge Sort?

When space is a constraint: Merge sort requires O(n) extra space for the temporary arrays. If space is limited, merge sort may not be suitable.

For small arrays: For small arrays (of size less than 100 elements), simpler sorting algorithms like insertion sort or bubble sort perform better than merge sort. The recursion overhead of merge sort outweighs its benefits for small arrays.

When stability is not important: If stability is not an issue, then quicksort would be a better choice. Quicksort does fewer comparisons than merge sort in practice and works in place without requiring extra space.

When the input is highly unsorted: For highly unsorted arrays, the merge step of merge sort becomes inefficient. A lot of time is wasted merging small sorted parts. In this case, Quicksort performs better.

In summary, avoid using merge sort:

• When space is limited
• For very small arrays
• When stability is not required
• For highly unsorted arrays

Pros and Cons of Merge Sort

Pros:

• Merge sort has a time complexity of O(n log n), which means that it can sort large amounts of data efficiently.
• It is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input list.
• Merge sort is a divide-and-conquer algorithm, which makes it easy to implement recursively and understand.
• Merge sort can also be used to efficiently merge two sorted lists into a single sorted list.

Cons:

• Merge sort requires additional memory to store the temporary arrays used during the sorting process, which can be a disadvantage when working with limited memory.
• The algorithm is not efficient for small lists, as the overhead of the recursive calls and array copying can outweigh the benefits of the sorting algorithm itself.
• Merge sort is not an in-place sorting algorithm, meaning that it requires additional memory to perform the sorting operation. This can be a disadvantage when working with large datasets or limited memory environments.