I just announced the new Spring Boot 2 material, coming in REST With Spring:

>> CHECK OUT THE COURSE

1. Introduction

In this tutorial, we’ll have a look at the Merge Sort algorithm and its implementation in Java.

Merge sort is one of the most efficient sorting techniques and it’s based on the “divide and conquer” paradigm.

2. The Algorithm

Merge sort is a “divide and conquer” algorithm wherein we first divide the problem into subproblems. When the solutions for the subproblems are ready, we combine them together to get the final solution to the problem.

This is one of the algorithms which can be easily implemented using recursion as we deal with the subproblems rather than the main problem.

The algorithm can be described as the following 2 step process:

  • Divide: In this step, we divide the input array into 2 halves, the pivot being the midpoint of the array. This step is carried out recursively for all the half arrays until there are no more half arrays to divide.
  • Conquer: In this step, we sort and merge the divided arrays from bottom to top and get the sorted array.

The following diagram shows the complete merge sort process for an example array {10, 6, 8, 5, 7, 3, 4}.

If we take a closer look at the diagram, we can see that the array is recursively divided into two halves until the size becomes 1. Once the size becomes 1, the merge processes come into action and start merging arrays back while sorting:

3. Implementation

For the implementation, we’ll write a mergeSort function which takes in the input array and its length as the parameters. This will be a recursive function so we need the base and the recursive conditions.

The base condition checks if the array length is 1 and it will just return. For the rest of the cases, the recursive call will be executed.

For the recursive case, we get the middle index and create two temporary arrays l[] and r[]. The mergeSort function is then called recursively for both the sub-arrays:

public static void mergeSort(int[] a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

    merge(a, l, r, mid, n - mid);
}

We then call the merge function which takes in the input and both the sub-arrays and the starting and end indices of both the sub arrays.

The merge function compares the elements of both sub-arrays one by one and places the smaller element into the input array.

When we reach the end of one of the sub-arrays, the rest of the elements from the other array are copied into the input array thereby giving us the final sorted array:

public static void merge(
  int[] a, int[] l, int[] r, int left, int right) {
 
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] < r[j]) {
            a[k++] = l[i++];
        }
        else {
            a[k++] = r[j++];
        }
    }
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }
}

The unit test for the program:

@Test
public void positiveTest() {
    int[] actual = { 5, 1, 6, 2, 3, 4 };
    int[] expected = { 1, 2, 3, 4, 5, 6 };
    MergeSort.mergeSort(actual, actual.length);
    assertArrayEquals(expected, actual);
}

4. Complexity

As merge sort is a recursive algorithm, the time complexity can be expressed as the following recursive relation:

T(n) = 2T(n/2) + O(n)

2T(n/2) corresponds to the time required to sort the sub-arrays and O(n) time to merge the entire array.

When solved, the time complexity will come to O(nLogn).

This is true for the worst, average and best case since it will always divide the array into two and then merge.

The space complexity of the algorithm is O(n) as we’re creating temporary arrays in every recursive call.

5. Conclusion

In this quick tutorial, we saw the working of the merge sort algorithm and how we can implement it in Java.

The entire working code is available over on GitHub.

I just announced the new Spring Boot 2 material, coming in REST With Spring:

>> CHECK OUT THE LESSONS

12
Leave a Reply

avatar
4 Comment threads
8 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
7 Comment authors
Loredana CrusoveanuEricTarunEugenkingslayer Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Naresh
Guest
Naresh

The code is not working. Looks like merge() has some issue

Loredana Crusoveanu
Editor

Hey Naresh,

I’m able to run the MergeSortUnitTest here: https://github.com/eugenp/tutorials/blob/master/algorithms-sorting/src/test/java/com/baeldung/algorithms/mergesort/MergeSortUnitTest.java successfully. What issue are you having?

simiyub
Guest
simiyub

This is excellent! By far the simplest and straightforward example I have come across in trying to understand merge sort- Thanks.
You could even do without passing in the length of the array and just pass in the array.

Loredana Crusoveanu
Editor

Glad you enjoyed the post!

The mergeSort() function takes the length as a parameter as well for the recursive calls inside the function like mergeSort(l, mid); But you can also overload this method with a version that only takes the array.

Cheers.

kingslayer
Guest
kingslayer

for the given array it does not work the last element does not get sorted
int [] arr = new int[] {99,85,1,25,20};

Loredana Crusoveanu
Editor

Hello,

I tested the code with this array as input as it was sorted correctly. Are you using our code from GitHub or a different one?

kingslayer
Guest
kingslayer

Hi loredana,

I tried the code from the above post however i tried checking the code from github
https://github.com/lor6/tutorials/tree/master/algorithms/src/main/java/com/baeldung/algorithms
i dint find merge sort, it would really be of great help if you can share github repo url.
Kudos for the post it is awesome

Loredana Crusoveanu
Editor

Hello, the code is in this repository: https://github.com/eugenp/tutorials/tree/master/algorithms-sorting The one you were looking at is only a fork.

kingslayer
Guest
kingslayer

Hi,

I made a mistake while calling the method from main method instead of passing the length of array i was passing length-1 so the last element was not getting sorted.
Anyways thanks a lott and the post is amazing

Eugen
Guest
Eugen

Hey KingSlayer – I’m glad you’re enjoying the post. Quick note – the comments are held in moderation until they’re approved, that’s why you don’t see the immediately

Tarun
Guest
Tarun

Hi i learn lots of thing from your blog thank you to provide great content . i have one suggestion please use black colour at list for code green is not readable thanks .

Eric
Member
Eric

Glad you found it helpful. All of our code examples use the same code formatter for consistency. We will keep the colors in mind if we make changes to our formatter in the future.
Cheers,
Eric