In this post, I will explain the Merge Sort algorithm and how to use it in Java.

Sorting is the process of arranging data in ascending or descending order. Sorting becomes necessary while searching a particular record in database, a particular telephone number in telephone directory, words in a dictionary, and so on.

In computer applications, sorting is a common operation, and there are several efficient algorithms to sort data. One such popular sorting algorithm is Merge Sort.

The Merge Sort Algorithm

Merge sort is basically a Divide and Conquer algorithm to sort a given set of elements recursively and then merge them. This algorithm runs in
O(n*log n) time in all cases, where n is the number of comparisons done.

Merge sort uses not-in-place sorting. In this type of sorting, the algorithm requires extra space for comparison and temporary storage of data elements. Therefore, for merge-sort, the required space is more than or equal to the elements being sorted. This is one of the drawback of Merge sort. However, with the cost of resources getting lesser, not-in-place sorting should not be a concern unless you are going for some extremely big data computation in an environment with limited resource.

To sort data, Merge Sort performs the following steps:

As you can see in this Figure, now we have single item in all the sub collections. At this point, we can say that, since each collection has only one item in it, everything is sorted.

When we were dividing, we were doubling the number of collections until we reached our base case of one item per collection.

Now, we’re doing the exact opposite in order to build our collection up.

This figure shows the complete process of Merge sort.

Implementing Merge Sort

An example of implementing Merge sort in Java is this.

        Comparable[] list2 = new Comparable[inputList.length list1.length];
        System.arraycopy(inputList, 0, list1, 0, list1.length);
        System.arraycopy(inputList, list1.length, list2, 0, list2.length);
        mergeSort(list1);
        System.arraycopy(list2, indexOfList2, resultList, indexOfMergedList, list2.length indexOfList2);

In this code, the
mergeSort() method takes an array to sort as input. If the input array has a single element, there is no need of sorting and the method just returns back the input array.

If the array has more than one element, the method splits the array into two halves, and sorts the splitted arrays recursively. The code then calls the
merge() method to merge the sorted array.

I’ve written a JUnit test to test the sorting function. If you are new to JUnit, I suggest going through my Junit series.

The
MergeSortExampleTest class is this.

public class MergeSortExampleTest {
        System.out.println(“Sorted array is: “ + Arrays.toString(arrayOfElements));
        assertThat(arrayOfElements).containsExactly(2, 4, 7, 9, 11, 13, 19);

The output on running the test in IntelliJ is this.

Merge sort is not the only algorithm for sorting data. Other sorting algorithms includes insertion sort, bubble sort, quicksort, and heap sort.

I won’t go into the details of comparing them in this post. I will leave you with few pointers on when to use Merge sort.

Share this:

This content was originally published here.