Merge Sort in Java

Today we are going to look into merge sort in Java.

I have been completing Leetcode’s explore page. They state that There are two approaches to implement the merge sort algorithm: top down or bottom up. Here, we will explain the top down approach as it can be implemented naturally using recursion.

LeetCode states The merge sort algorithm can be divided into three steps, like all divide-and-conquer algorithms:

• Divide the given unsorted list into several sublists. (Divide)
• Sort each of the sublists recursively. (Conquer)

Merge the sorted sublists to produce new sorted list. (Combine)

• In the first step, we divide the list into two sublists. (Divide)
• Then in the next step, we recursively sort the sublists in the previous step. (Conquer)
• Finally we merge the sorted sublists in the above step repeatedly to obtain the final list of sorted elements. (Combine)

The recursion in step (2) would reach the base case where the input list is either empty or contains a single element

Now, we have reduced the problem down to a merge problem, which is much simpler to solve. Merging two sorted lists can be done in linear time complexity {O(N)}O(N), where {N}N is the total lengths of the two lists to merge.

First we recursively split the arrays into two subarrays until the length of the array is less than or equal to 1.

public class Solution {
    
    public int [] merge_sort(int [] input) {
      if (input.length <= 1) {
        return input;
      }
      int pivot = input.length / 2;
      int [] left_list = merge_sort(Arrays.copyOfRange(input, 0, pivot));
      int [] right_list = merge_sort(Arrays.copyOfRange(input, pivot, input.length));
      return merge(left_list, right_list);
    }

When it hits the base case it will compare the two list two each other and combine them. We create a new area with the length or the two arrays.

public int [] merge(int [] left_list, int [] right_list) {
      int [] ret = new int[left_list.length + right_list.length];
      int left_cursor = 0, right_cursor = 0, ret_cursor = 0;
while (left_cursor < left_list.length && 
             right_cursor < right_list.length) {
        if (left_list[left_cursor] < right_list[right_cursor]) {
          ret[ret_cursor++] = left_list[left_cursor++];
        } else {
          ret[ret_cursor++] = right_list[right_cursor++];
        }
      }
      

Then we have to add all of the remaining elements in the array left.

while (left_cursor < left_list.length) {
        ret[ret_cursor++] = left_list[left_cursor++];
      }
      while (right_cursor < right_list.length) {
        ret[ret_cursor++] = right_list[right_cursor++];
      }  
      return ret;
    }

There you have it merge sort. One of the faster sorting algorithms. Here is the full code.

public class Solution {
    
    public int [] merge_sort(int [] input) {
      if (input.length <= 1) {
        return input;
      }
      int pivot = input.length / 2;
      int [] left_list = merge_sort(Arrays.copyOfRange(input, 0, pivot));
      int [] right_list = merge_sort(Arrays.copyOfRange(input, pivot, input.length));
      return merge(left_list, right_list);
    }
    
    public int [] merge(int [] left_list, int [] right_list) {
      int [] ret = new int[left_list.length + right_list.length];
      int left_cursor = 0, right_cursor = 0, ret_cursor = 0;
while (left_cursor < left_list.length && 
             right_cursor < right_list.length) {
        if (left_list[left_cursor] < right_list[right_cursor]) {
          ret[ret_cursor++] = left_list[left_cursor++];
        } else {
          ret[ret_cursor++] = right_list[right_cursor++];
        }
      }
      // append what is remain the above lists
      while (left_cursor < left_list.length) {
        ret[ret_cursor++] = left_list[left_cursor++];
      }
      while (right_cursor < right_list.length) {
        ret[ret_cursor++] = right_list[right_cursor++];
      }  
      return ret;
    }
}

I only explained the Top Down Approach. If you want the bottom up approach check out Leet Codes Explore page Recursion II.