Merge Sort in Java

In this article, we will look at the merge sort in Java. We will discuss the merge sort algorithm and its implementation in Java.

 

Introudction

The merge sort is a divide and conquer algorithm. It works on the principle of dividing the problem into subproblems recursively and then combine them together to get the final output (Sorted elements). We base algorithm on the recursion technique. Let’s look at the high level flow for the merge sort algorithm in Java.

 

1. Mere Sort Algorithm Overview

Before we jump in the code, let’s try to understand the basic principle of merge sort algorithm:

  1. During merge sort, we divide the array or collection into two sub collections.
  2. To divide the array, we take the middle of the array and split in into left and right array.
  3. The split process will continue until we have only 1 element in the array (Since we need not sort the 1 element and this is the main concept for the merge sort algorithm.) 
  4. Once we get to the single elements, we will combine the results of the 2 arrays by comparing and putting them in sorted order.

Because of the above workflow, we call this as divide and conquer algorithm.

Divide: It is the first step, we divide the problem into subproblems. We are dividing the array into 2 halves.

Conquer: This step involves sorting and merging back the array.

Let’s look at the following example to understand the workflow and how this algorithm works

Merge Sort in Java

Numbers in red shows the order in which merge sort executes steps.

 

2. Merge Sort Implementation

Let’s see how to implementation merge sort in Java. The example contains a lot of documentation to give you a clear explanation of the logic but we will cover each steps of the algorithm. 

public class MergeSortAlgo {

    public static void main(String[] args) {

        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        int[] temp = new int[input.length];  // Temp array to store split results.
        quickSort(input, 0 , input.length-1, temp);
        
        for(int i =0; i< input.length; i++){
            System.out.println(input[i]);
        }
    }

    private static void quickSort(int[] array, int start, int end, int[] temp){
        /**
         * We only want to split it until the start is less than the end.We don't want to go beyond
         * this point.
         */
        if(start < end) {

            // We need to find a point to split the array.We will find the midpoint.
            int mid = (start + end) / 2;

            /**
             * Now, we will split the array until it is small enough to be sorted (only one element).
             * We will split the array from the starting point till mid and from mid point till the end.
             * Please refer to the picture above to see how the split process works.
             */
            quickSort(array, start, mid, temp);
            quickSort(array, mid + 1, end, temp);

            /**
             * Time to sort and split back the given input.
             */
            merge(array,temp,start,end,mid);
        }
    }

    private static void merge(int[] array, int[] temp, int start, int end, int mid){

        /* Copy both side in to our temp array */
        for(int i =start ; i<= end ; i++){
            temp[i] = array[i];
        }
        // let's sort and merge back the array

        int i = start; // start will become left
        int j = mid+1;  // this is the starting point for our where right hand of the array was copied in helper
        int current = start; // position where we like to sort and merge

        /**
         * We will iterate through the temp array.Compare the right and left half , copy the smallest element from the 2 array to
         * the original array/
         */
        while(i <=mid && j <= end){
            if(temp[i] <=temp[j]){
                array[current] = temp[i];
                i++;
            }
            else{
                /**
                 * If right element is smaller than left element.
                 */
                array[current] = temp[j];
                j++;
            }
            /**
             * we increment current position only when we got a match.This can be added to both if and else sections but
             * we will keep it in a common place to avoid code duplication
             */
            current++;
        }

        /**
         * Copy rest of the left side of the array in to the target array
         */
        int remaining= mid -i;
        for (int k = 0 ; k<= remaining; k++){
            array[current+k] = temp[i+k];
        }
    }
}

Let’s try to inspect some important points

if (start < end) {
  int mid = (start + end) / 2;
  quickSort(array, start, mid, temp);
  quickSort(array, mid + 1, end, temp);
  merge(array, temp, start, end, mid);
}

We are performing following important task in this code

  1. We find the middle point for the input.
  2. We recursively calling the quickSort method for the left and right side of the midpoint. (creating 2 sub arrays)
  3. Recursive method works until the start is greater than the end.
  4. Finally, we are calling merge method to which takes the input and both the sub-arrays and merge them together in the sorted fashion.

 

private static void merge(int[] array, int[] temp, int start, int end, int mid){

    for(int i =start ; i<= end ; i++){
        temp[i] = array[i];
    }

    int i = start; // start will become left
    int j = mid+1;  // this is the starting point for our where right hand of the array was copied in helper
    int current = start; // position where we like to start sorting and merge

    while(i <=mid && j <= end){
        if(temp[i] <=temp[j]){
            array[current] = temp[i];
            i++;
        }
        else{
            array[current] = temp[j];
            j++;
        }
        current++;
    }
    int remaining= mid -i;
    for (int k = 0 ; k<= remaining; k++){
        array[current+k] = temp[i+k];
    }
}

Our merge method sorts and merging the 2 arrays. Let’s see few important points for this method

  1. Method needs start and end point of the arrays along with the original array (we need this original array to sort the final output).
  2. Need the midpoint for both the arrays.We need this to while sorting the left and right side of the array.
  3. To keep sorting simple, we are using a temp array. We use this array to a temporary store both the sub array before our the sort and merge operation.
  4. In the while loop we iterate through the temp array and put the element in the right position in the original array.
  5. At the end of the while loop, one side is already in the right position, so we just copy the left side of the array in the target position.

 

3. Time Complexity

The merge sort algorithm is a recursive algorithm. We can express the time complexity as

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

the time complexity will come to O(nLogn).Here are some additional information for the quick sort algorithm:

  • Space Complexity  – O(n) 
  • In place Sorting – Not for most of the cases.
  • Time complexity for worst, average and best cases is always O(nLogn) as merge sort always divides the array into two halves.

 

4. Merge Sort Applications

Here are some typical use cases where merge sort is the right choice for us.

  1. In case data structure does not support random access. We use it in many external sorting use cases.
  2. Linked list is another good example where merge sort is powerful and very quick. This is possible since it is easy to change the pointer in the linked list during the merge.
  3. You can use merge sort when you need a stable sort. It’s very important feature of merge sort.

 

Summary

In this article, we saw the merge sort in Java. We discussed the various steps to understand the merge sort algorithm. In the end of this article, we saw when merge sort algorithm is a perfect choice for your sorting problem.

Java Development Journal

Hello!! Welcome to the Java Development Journal. We love to share our knowledge with our readers and love to build a thriving community.

follow me on:

Leave a Reply

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of