Sorting Frenzy 2 - Merge Sort

Introduction

Today I want to talk to you about Merge Sort ! The algorithm is kind of similar to Quick Sort and that’s why this is the second sorting algo.

What is Quick Sort?

In computer science, merge sort (also commonly spelled as mergesort or merge-sort) is an efficient and general purpose comparison-based sorting algorithm. Most implementations of merge sort are stable, which means that the relative order of equal elements is the same between the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. - Wikipedia

Like Quick Sort, Merge Sort is a type of divide and conquer algorithm. Instead of finding a pivot, it divides the array in half until the sub-array is of length 1. And then joins it back together while sorting.

In this post, we’ll analyze a standard Merge Sort implementation and benchmark it with an array of 1,000,000 elements.

The code we will be analyzing:

  private static void mergeArrays(int[] arr, int low, int mid, int high) {
        int[] left = Arrays.copyOfRange(arr, low, mid + 1);
        int[] right = Arrays.copyOfRange(arr, mid + 1, high + 1);

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

        while (i < left.length && j < right.length) {
            arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
        }

        while (i < left.length) arr[k++] = left[i++];
        while (j < right.length) arr[k++] = right[j++];
    }

  private static void mergeSort(int[] arr, int low, int high) {
    if (low>=high) {
      return;
    }

    int mid = low + ((high-low)/2);

    mergeSort(arr, low, mid);
    mergeSort(arr, mid+1, high);

    mergeArrays(arr, low, mid, high);
  }

Lets break it down

Method mergeSort

This is the main method of the sort. Receives an array and two integers. The integers low and high define the sub-array that we are checking.

When entering we have the base case. In case the low and the high are the same, it means that the sub array is non-existant so we want to exit the method.

After that, we find the mid of the array and call the function recursively for each side. After the recursive calls, we want to merge the arrays back together and for that we have the function mergeArrays

Method mergeArrays

This function seems complicated but in reality what it is doing is quite simple. We are joining two arrays while sorting them. We use the technique of two pointer. This means that each sub-array gets one assigned one pointer that points to the first index. Then, we check both values and find the lower one and add that on the original arr. We continue to do this until there is no more elements.

Important Note!

The code above is doing the merge sort in-place. This means that, instead of creating multiple arrays, we are changing the original one. Of course, this complicates a bit the logic but it allow us to do it much faster. In this way, we are not wasting excessive memory keeping track of dozens of sub-arrays.

If you prefer a visual representation, below is a gif from Wikipedia Commons:

MergeSort GIF

Performance Analysis

Time Complexity: O(n log n)

Because we always split the array exactly in half, the depth of the recursion is consistently log2(1,000,000) that is approx 20. At each of those 20 levels, we touch all $n$ elements once to merge them. This results in the O(n log n) complexity regardless of the input data.

Space Complexity: O(n)

Even though we call this “In-Place” to distinguish it from the version that creates new arrays (Arrays.copyOfRange), Merge Sort mathematically requires O(n) extra space to store elements temporarily during the merge.

Benchmarking the Results

Using a function to measure the duration, we tested this implementation with a randomized array of 1,000,000 integers.

public static void main(String[] args) {
    int[] randomArray = ArrayUtils.generateRandomIntegerArray(1_000_000, 1, 1_000_000);

    measure(String.format("Merge Sort array with %d elements", randomArray.length),
            () -> mergeSort(randomArray, 0, randomArray.length-1));

    if (ArrayUtils.checkSortedArray(randomArray)) {
        System.out.println("Array is Sorted!");
    } else {
        System.out.println("Array is not Sorted!");
    }

}

When running this, the results are impressive:

Merge Sort array with 1000000 elements took 216,890 ms
Array is Sorted!

The algorithm processed a million integers in roughly 216 ms! While Quick Sort is often slightly faster in practice due to better cache locality, Merge Sort’s consistent O(n log n) performance makes it the gold standard for scenarios where you cannot afford a O(n^2) “worst-case” scenario. This predictability is why Merge Sort (and its variant, Timsort) is the default for sorting Objects in Java’s Arrays.sort().

Conclusion

Merge Sort remains a foundational algorithm for any developer, valued for its stability and guaranteed efficiency. Its “Divide and Conquer” strategy allows it to handle vast amounts of data with a mathematical certainty that few other algorithms can match.

However, remember that Merge Sort’s main trade-off is its O(n) space complexity. Even an “in-place” recursive structure requires that auxiliary memory to perform the merge. Modern production libraries often use “Hybrid” approaches—for example, switching to Insertion Sort when the sub-array size drops below a certain threshold (usually 7–15 elements) to avoid the overhead of recursive calls on tiny fragments of data.

The code for this post can be found in my github.

Happy coding!

← Back to blog

Table of contents