Core Java

Merge Sort Java algorithm – Code Example

In this article, we will discuss about the Merge Sort Java algorithm, which is much more efficient than some of the other sorting algorithms.

Generally, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

You can also check this tutorial in the following video:

1. When should the Merge Sort Java algorithm be applied?

The Mergesort works by sorting and merging two arrays into one. The basic concept of the Mergesort algorithm is the merging of two already sorted-arrays into one array.

Mergesort is good for slowly accessed data. Like a linked list which is random-accessed. The Arrays.sort() method uses Mergesort or Quicksort depending on the type of array being sorted. When the length is lower than 7 elements the insertion sort is used. If data is fast accessed and located in memory then Quicksort is almost always outperforming Mergesort.

1. What is the complexity of Mergesort?

The time it takes to sort an array with Mergesort can be described by the formula:

T(n) = Θ(n * log(n))

Since the mergesort algorithm uses the same systematic approach for any array this formula is both the worst case and average case running time.

Where “T(n)” is the time it takes to run the algorithm for the list or array.

The “Θ”-symbol just means that it is a function of n * lg (n).

“n” is the number of elements in the array.

“lg(n)” is the 10-logorithmic value of the number of elements.

We can describe the formula in clear text in stead:

Time-to-sort-in-seconds = c * n * lg (n) / computations-per-second-for-the-used-computer Here c is a constant that depends on the implementation (developer) of the mergesort and the chosen compiler.

2. The strategy behind mergesort

Let’s see the strategy behind merge sort. The following diagram shows how the Merge sort java algorithm first splits up the array elements into smallest possible arrays. Then the arrays are merged and sorted.

The trick that makes this algorithm efficient is that it is very fast to compare and merge 2 arrays when we know that the 2 arrays individually already are sorted.

It is a recursive algorithm since the methods are calling themselves until the main array is split up into arrays with only 1 element.

Then another recursive call is made to merge 2 arrays at a time.

This is how the compare and merge works. 1 index per array is used to keep track of the position to compare for each iteration. This can be done because we know that each array is sorted from left to right.

In the next section, will show how merging works in the Mergesort algorithm.

3. Merging two sorted arrays

The merging is done by combining two already sorted arrays into one empty array. Let us say that we have two sorted arrays A and B of size 5 and 7. These two arrays will merge into an array C of size 12.

The merging starts by comparing the items one by one from both the sorted arrays, inserting the smaller item into the third array C and incrementing the cursor of the array of the smaller item by one. The process continues until the cursor of any one sorted array scans and compares all the items of the array. Please note that the two arrays do not require to be of the same size.

Let us have an example of merging two sorted arrays.

MergingExample.java

 010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 `package` `com.javacodegeeks.sorting.mergesort;` `public` `class` `MergingExample {` `    ` `    ``public` `static` `void` `main(String[] args) {``        ``int` `[]a = {``2``,``15``,``22``,``47``,``51``};``        ``int` `[]b = {``14``,``18``,``26``,``45``,``49``,``56``,``78``};``        ` `        ``// Array C of sum of size of the two sorted array A and B``        ``int` `[]c = ``new` `int``[a.length+b.length];``        ` `        ``merge(a,b,c);``        ``System.out.print(``"Array a: "``);``        ``printArray(a);``        ``System.out.println();``        ``System.out.print(``"Array b: "``);``        ``printArray(b);``        ``System.out.println();``        ``System.out.print(``"Array c: "``);``        ``printArray(c);``    ``}` `    ``public` `static` `void` `merge(``int` `[]a, ``int` `[]b, ``int` `[]c){``        ``int` `cursorA = ``0``,cursorB = ``0``,cursorC = ``0``;``        ``int` `sizeA = a.length;``        ``int` `sizeB = b.length;``        ` `        ``// Runs until neither array is empty``        ``while``(cursorA < sizeA && cursorB < sizeB){``            ``// Compare the items of two arrays and copy the smaller item into to third array``            ``if``(a[cursorA] < b[cursorB]){``                ``c[cursorC++] = a[cursorA++];``            ``}``else``{``                ``c[cursorC++] = b[cursorB++];``            ``}``        ``}``        ` `        ``// If array B's cursor scanned and compared all the items of the array``        ``// but array A's is not``        ``while``(cursorA < sizeA){``            ``c[cursorC++] = a[cursorA++];``        ``}``        ` `        ``// If array A's cursor scanned and compared all the items of the array``        ``// but array B's is not``        ``while``(cursorB < sizeB){``            ``c[cursorC++] = b[cursorB++];``        ``}``    ``}``    ` `    ``public` `static` `void` `printArray(``int` `[]array){``        ``for``(``int` `i : array){``            ``System.out.print(i+``" "``);``        ``}``    ``}``}`

If we run the above code, we will have the following results:

 123 `Array a: 2 15 22 47 51 ``Array b: 14 18 26 45 49 56 78 ``Array c: 2 14 15 18 22 26 45 47 49 51 56 78 `

In the above example, we took two sorted arrays `a` and `b` of sizes 5 and 7 and merged them into the third array `c`. Please note that we created the array `c` of size equal to the sum of the two sorted arrays.

The `merge()` method takes three arrays as parameters, the two sorted arrays `a` and `b` and an empty array `c` which stores the sorted items of the both arrays. We initialized three cursors each pointed to their respective array at position 0. The method runs by the three loops. The first loop runs until neither array `a` or `b` get scanned completely. The items from both the arrays get compared and the smaller item copied into the array `c`. Then the cursor of the smaller items array and array `c` increments to one.

The second while loop runs if, the array `b` is completely scanned out, but there are items left in the array `a`. It copies all left items of the array `a` to the array `c`. The third loop works similarly, only if, the array `a` completely scanned out but items left in the array `b`. It copies all left items of the array `b` to the array `c`.

Now, we have seen how to merge the two sorted arrays. Let’s see how to sort an array using the Java Merge sort algorithm.

4. Sorting using Merge Sort Java algorithm

The sorting is done using the Mergesort by dividing an array into two sub-arrays, sort each of them, and then merge them into one. The sorting in the two divided sub-arrays are done by again dividing them further until you reach a sub-array with only one item in it. An array containing only one item is assumed to be as sorted.

MergesortExample.java

 01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 `package` `com.javacodegeeks.sorting.mergesort;` `public` `class` `MergesortExample {` `    ``private` `static` `int` `[]a;``    ``public` `static` `void` `main(String[] args) {``        ``a = getArray();``        ``printArray(a);``        ``sort();``        ``System.out.println();``        ``printArray(a);``    ``}``    ` `    ``public` `static` `void` `sort(){``        ``int` `[]tempArray = ``new` `int``[a.length];``        ``mergeSort(tempArray,``0``,a.length-``1``);``    ``}``    ` `    ``public` `static` `void` `mergeSort(``int` `[]tempArray,``int` `lowerIndex,``int` `upperIndex){``        ``if``(lowerIndex == upperIndex){``            ``return``;``        ``}``else``{``            ``int` `mid = (lowerIndex+upperIndex)/``2``;``            ``mergeSort(tempArray, lowerIndex, mid);``            ``mergeSort(tempArray, mid+``1``, upperIndex);``            ``merge(tempArray,lowerIndex,mid+``1``,upperIndex);``        ``}``    ``}``    ` `    ``public` `static` `void` `merge(``int` `[]tempArray,``int` `lowerIndexCursor,``int` `higerIndex,``int` `upperIndex){``        ``int` `tempIndex=``0``;``        ``int` `lowerIndex = lowerIndexCursor;``        ``int` `midIndex = higerIndex-``1``;``        ``int` `totalItems = upperIndex-lowerIndex+``1``;``        ``while``(lowerIndex <= midIndex && higerIndex <= upperIndex){``            ``if``(a[lowerIndex] < a[higerIndex]){``                ``tempArray[tempIndex++] = a[lowerIndex++];``            ``}``else``{``                ``tempArray[tempIndex++] = a[higerIndex++];``            ``}``        ``}``        ` `        ``while``(lowerIndex <= midIndex){``            ``tempArray[tempIndex++] = a[lowerIndex++];``        ``}``        ` `        ``while``(higerIndex <= upperIndex){``            ``tempArray[tempIndex++] = a[higerIndex++];``        ``}``        ` `        ``for``(``int` `i=``0``;i

If we run the above code, we will have the following results:

 12 `96 51 20 98 38 73 23 22 47 30 ``20 22 23 30 38 47 51 73 96 98 `

In the above example, we have sort an array using the Mergesort. The example has an array `a` which gets sorted using the Mergesort. The `sort()` method, initializes a temp array and internally calls the `mergeSort()` method which performs the merge sort on the array `a`. The temp array is used to store items of the array `a` temporally.

The `mergeSort()` method is the recursive method and has three parameters, a `tempArray`, a `lowerIndex` and a `upperIndex` of the array to be sorted i.e of the array `a`. The other important method used in the above example is the `merge()` method which is used to merge the two sub-arrays in one array. In the above example, we have not used multiple arrays, we applied limit boundaries to virtually divide an array into multiple sub-arrays.

Let us have a deeper look into these methods.

`mergeSort(int []tempArray,int lowerIndex,int upperIndex)`: The `mergeSort()` method is used to merge sort the given array. It passes three parameters, the `tempArray` is used as temporally array, and the `lowerIndex` and the `upperIndex` is used to divide the array virtually into different sub-arrays.

`if(lowerIndex == upperIndex)`: The `if` statement is the base statement of this recursive method. If the `lowerIndex` and the `upperIndex` are equal that means there is only one item in the array (or sub-array) and does not need to be divided any further.

`int mid = (lowerIndex+upperIndex)/2`: The `mid` is used to divide the array or the sub-array into half.

`mergeSort(tempArray, lowerIndex, mid)`: Recursive call to the method, but with different parameters from the `lowerIndex` to the `mid` index of the array.

`mergeSort(tempArray, mid+1, upperIndex)`: Recursive call to the method, but with different parameters from the `mid+1` index to the `upperIndex` of the array.

`merge(tempArray,lowerIndex,mid+1,upperIndex)`: The `merge()` method is used to merge the sorted array.

The concept we used in dividing an array is by restricting the `lowerIndex` and the `upperIndex` of the array. Hence, consider the array as a sub-array of the size `upperIndex-lowerIndex+1`. The merge() method is used to combine the items of that virtually divided sub-arrays in a sorted order starts from the smallest item and ends with the largest item.

The four main fields used in this method are the `lowerIndex`, `midIndex`, `higherIndex` and the `upperIndex`. These fields are the restriction indexes used to set boundaries in between the array and provides virtually separated sub-arrays.

`while(lowerIndex <= midIndex && higerIndex <= upperIndex)`: The loop works until the `lowerIndex` is smaller than or equal to the `midIndex` and the `higerIndex` is smaller than or equal to the `upperIndex` of the array `a`. It means neither of the virtual sub-array is scanned completely.

The next lines of code checks, if the item in the array `a` at the position pointed by the `lowerIndex` is smaller than the item in the array `a` pointed by the `higerIndex`, then it will be copied to the `tempArray`. Otherwise, the item at the `higerIndex` would be copied. These comparisons are used to position the items in sorted order. We copied the smaller item first, and then the next larger one and so on until neither of the limit set for this virtual sub-array is reached.

The two sub-arrays might not be of the same size. So, there could be some cases when the limit is reached for the one sub-array, but not for the other sub-array. Then there is no need for comparison and the next two while loops are used to simply copy the items into the `tempArray`.

Later, when all the items from the two sub-arrays are copied in sorted order into the `tempArray`, we override them into the main array `a`. The above process continues with the different sub-arrays until the all items gets compared and places into their proper sorted place which results into the complete sorted array.

5. Sorting in descending order using Mergesort

So far, we have sort an array in ascending order, i.e. from the smallest item to the largest item. But by making a small change in the algorithm, we can sort an array in descending order, i.e. from the largest item to the smallest item.

MergesortDescendingExample.java

 01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 `package` `com.javacodegeeks.sorting.mergesort;` `public` `class` `MergesortDescendingExample {` `    ``private` `static` `int` `[]a;``    ``public` `static` `void` `main(String[] args) {``        ``a = getArray();``        ``printArray(a);``        ``sort();``        ``System.out.println();``        ``printArray(a);``    ``}` `    ``public` `static` `void` `sort(){``        ``int` `[]tempArray = ``new` `int``[a.length];``        ``mergeSort(tempArray,``0``,a.length-``1``);``    ``}` `    ``public` `static` `void` `mergeSort(``int` `[]tempArray,``int` `lowerIndex,``int` `upperIndex){``        ``if``(lowerIndex == upperIndex){``            ``return``;``        ``}``else``{``            ``int` `mid = (lowerIndex+upperIndex)/``2``;``            ``mergeSort(tempArray, lowerIndex, mid);``            ``mergeSort(tempArray, mid+``1``, upperIndex);``            ``merge(tempArray,lowerIndex,mid+``1``,upperIndex);``        ``}``    ``}` `    ``public` `static` `void` `merge(``int` `[]tempArray,``int` `lowerIndexCursor,``int` `higerIndex,``int` `upperIndex){``        ``int` `tempIndex=``0``;``        ``int` `lowerIndex = lowerIndexCursor;``        ``int` `midIndex = higerIndex-``1``;``        ``int` `totalItems = upperIndex-lowerIndex+``1``;``        ``while``(lowerIndex <= midIndex && higerIndex <= upperIndex){``            ``if``(a[lowerIndex] > a[higerIndex]){``                ``tempArray[tempIndex++] = a[lowerIndex++];``            ``}``else``{``                ``tempArray[tempIndex++] = a[higerIndex++];``            ``}``        ``}` `        ``while``(lowerIndex <= midIndex){``            ``tempArray[tempIndex++] = a[lowerIndex++];``        ``}` `        ``while``(higerIndex <= upperIndex){``            ``tempArray[tempIndex++] = a[higerIndex++];``        ``}` `        ``for``(``int` `i=``0``;i

If we run the above code, we will have the following results:

 12 `80 9 42 27 92 47 39 40 49 71 ``92 80 71 49 47 42 40 39 27 9 `

In the above example, we have Mergesort the given array in a descending order. By making a small change in the program, we have sorted the array in descending order, i.e. items get sorted in an order starts from the largest item at the first index of the array and goes on to the smallest item at the last position in the array.

`if(a[lowerIndex] > a[higerIndex])`: The only change we have made is in the comparison of the two items in the sub-arrays. This time the larger item gets copied into the `tempArray` instead of the smaller item. By making this change, the largest item comes at the first position of the array, then the next item, smaller than the item at the first position, and so on, until the last position which contains the smallest item in the array.

The rest of the code remains the same.

6. Mergesort Objects

So far, we have sort an array of integers. In this section, we will see how to sort objects of any type using the Mergesort. We will do this, by creating a sorting utility class, which contains static methods that provides different variations to sort a given array of any class. The utility class contains overloading `sort()`, in order to provide a variety of sorting options to the given array.

SortingUtility.java

 001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193 `package` `com.javacodegeeks.sorting.utility;` `import` `java.util.Comparator;``/*`` ``* The utility class which contains static methods.`` ``* */``public` `class` `SortingUtility {`  `    ``// order constants which tells at what order the array should be sort``    ``public` `static` `final` `int` `ASC_ORDER = ``1``;``    ``public` `static` `final` `int` `DESC_ORDER = ``2``;` `    ``/* We want this class as a utility class that contains only static methods.``     ``* So, avoiding any creation of an object of this class by keeping its``     ``* constructor as private and also throwing an AssertionError to avoid ``     ``* any accidently creation of an object within the class. ``     ``* */``    ``private` `SortingUtility(){``        ``throw` `new` `AssertionError();``    ``}` `    ``public` `static``> ``void` `sort(T []a){``        ``mergeSort(a,``0``, a.length-``1``, ASC_ORDER);``    ``}` `    ``public` `static`` ``void` `sort(T []a, Comparatorcomparator){``        ``mergeSort(a,``0``, a.length-``1``, ASC_ORDER,comparator);``    ``}` `    ``public` `static``> ``void` `sort(T []a,``int` `order){``        ``mergeSort(a,``0``, a.length-``1``, order);``    ``}` `    ``public` `static`` ``void` `sort(T []a,``int` `order, Comparatorcomparator){``        ``mergeSort(a,``0``, a.length-``1``, order,comparator);``    ``}` `    ``public` `static``> ``void` `mergeSort(T []a,``int` `lowerIndex,``int` `upperIndex,``int` `order){``        ``if``(lowerIndex == upperIndex){``            ``return``;``        ``}``else``{``            ``int` `mid = (lowerIndex+upperIndex)/``2``;``            ``mergeSort(a,lowerIndex,mid,order);``            ``mergeSort(a,mid+``1``,upperIndex,order);` `            ``if``(order == ASC_ORDER){``                ``mergeAsc(a,lowerIndex,mid+``1``,upperIndex);``            ``}``else` `if``(order == DESC_ORDER){``                ``mergeDesc(a,lowerIndex,mid+``1``,upperIndex);``            ``}``else``{``                ``throw` `new` `UnsupportedOperationException(``"The order you specified is not supported."``);``            ``}``        ``}``    ``}` `    ``public` `static`` ``void` `mergeSort(T []a,``int` `lowerIndex,``int` `upperIndex,``int` `order, Comparatorcomparator){``        ``if``(lowerIndex == upperIndex){``            ``return``;``        ``}``else``{``            ``int` `mid = (lowerIndex+upperIndex)/``2``;``            ``mergeSort(a,lowerIndex,mid,order,comparator);``            ``mergeSort(a,mid+``1``, upperIndex,order,comparator);` `            ``if``(order == ASC_ORDER){``                ``mergeAsc(a,lowerIndex,mid+``1``,upperIndex,comparator);``            ``}``else` `if``(order == DESC_ORDER){``                ``mergeDesc(a,lowerIndex,mid+``1``,upperIndex,comparator);``            ``}``else``{``                ``throw` `new` `UnsupportedOperationException(``"The order you specified is not supported."``);``            ``}``        ``}``    ``}` `    ``@SuppressWarnings``(``"unchecked"``)``    ``public` `static``> ``void` `mergeAsc(T []a,``int` `lowerIndexCursor,``int` `higerIndex,``int` `upperIndex){``        ``Object []tempArray = getTempArray(a.length);``        ``int` `tempIndex=``0``;``        ``int` `lowerIndex = lowerIndexCursor;``        ``int` `midIndex = higerIndex-``1``;``        ``int` `totalItems = upperIndex-lowerIndex+``1``;``        ``while``(lowerIndex <= midIndex && higerIndex <= upperIndex){``            ``if``(((Comparable)a[lowerIndex]).compareTo(a[higerIndex]) < ``0``){``                ``tempArray[tempIndex++] = a[lowerIndex++];``            ``}``else``{``                ``tempArray[tempIndex++] = a[higerIndex++];``            ``}``        ``}` `        ``while``(lowerIndex <= midIndex){``            ``tempArray[tempIndex++] = a[lowerIndex++];``        ``}` `        ``while``(higerIndex <= upperIndex){``            ``tempArray[tempIndex++] = a[higerIndex++];``        ``}` `        ``for``(``int` `i=``0``;i ``void` `mergeAsc(T []a,``int` `lowerIndexCursor,``int` `higerIndex,``int` `upperIndex,Comparatorcomparator){``        ``Object []tempArray = getTempArray(a.length);``        ``int` `tempIndex=``0``;``        ``int` `lowerIndex = lowerIndexCursor;``        ``int` `midIndex = higerIndex-``1``;``        ``int` `totalItems = upperIndex-lowerIndex+``1``;``        ``while``(lowerIndex <= midIndex && higerIndex <= upperIndex){``            ``if``(comparator.compare(a[lowerIndex],a[higerIndex]) < ``0``){``                ``tempArray[tempIndex++] = a[lowerIndex++];``            ``}``else``{``                ``tempArray[tempIndex++] = a[higerIndex++];``            ``}``        ``}` `        ``while``(lowerIndex <= midIndex){``            ``tempArray[tempIndex++] = a[lowerIndex++];``        ``}` `        ``while``(higerIndex <= upperIndex){``            ``tempArray[tempIndex++] = a[higerIndex++];``        ``}` `        ``for``(``int` `i=``0``;i> ``void` `mergeDesc(T []a,``int` `lowerIndexCursor,``int` `higerIndex,``int` `upperIndex){``        ``Object []tempArray = getTempArray(a.length);``        ``int` `tempIndex=``0``;``        ``int` `lowerIndex = lowerIndexCursor;``        ``int` `midIndex = higerIndex-``1``;``        ``int` `totalItems = upperIndex-lowerIndex+``1``;``        ``while``(lowerIndex <= midIndex && higerIndex <= upperIndex){``            ``if``(((Comparable)a[lowerIndex]).compareTo(a[higerIndex]) > ``0``){``                ``tempArray[tempIndex++] = a[lowerIndex++];``            ``}``else``{``                ``tempArray[tempIndex++] = a[higerIndex++];``            ``}``        ``}` `        ``while``(lowerIndex <= midIndex){``            ``tempArray[tempIndex++] = a[lowerIndex++];``        ``}` `        ``while``(higerIndex <= upperIndex){``            ``tempArray[tempIndex++] = a[higerIndex++];``        ``}` `        ``for``(``int` `i=``0``;i ``void` `mergeDesc(T []a,``int` `lowerIndexCursor,``int` `higerIndex,``int` `upperIndex,Comparatorcomparator){``        ``Object []tempArray = getTempArray(a.length);``        ``int` `tempIndex=``0``;``        ``int` `lowerIndex = lowerIndexCursor;``        ``int` `midIndex = higerIndex-``1``;``        ``int` `totalItems = upperIndex-lowerIndex+``1``;``        ``while``(lowerIndex <= midIndex && higerIndex <= upperIndex){``            ``if``(comparator.compare(a[lowerIndex],a[higerIndex]) > ``0``){``                ``tempArray[tempIndex++] = a[lowerIndex++];``            ``}``else``{``                ``tempArray[tempIndex++] = a[higerIndex++];``            ``}``        ``}` `        ``while``(lowerIndex <= midIndex){``            ``tempArray[tempIndex++] = a[lowerIndex++];``        ``}` `        ``while``(higerIndex <= upperIndex){``            ``tempArray[tempIndex++] = a[higerIndex++];``        ``}` `        ``for``(``int` `i=``0``;i

The above class `SortingUtility` is a utility class which contains static methods used to sort a given array of a type `T`. The class contains overloaded `sort()` methods. These `sort()` methods internally call the `mergeSort()` method to sort the given array.

`public static final int ASC_ORDER = 1;` : The constant field is used as a flag, if set, the sorting would be done in ascending order.

`public static final int DESC_ORDER = 2;` : The constant field is used as a flag, if set, the sorting would be done in descending order.

`public static<T extends Comparable<T>> void sort(T []a)`:This method is used to sort a given array of a type `T`. The class `T` should implement the `Comparable` interface and provide an implementation of the overridden `comparTo()` method, otherwise, it will throw a `ClassCastException`. Internally, it calls the `mergeSort()` method which sorts the array in ascending order. It also has a `tempArray` which is an empty array of size equals to the size of the array `a`, used temporally to store items of the array `a`.

`public static<T> void sort(T []a, Comparator<? super T>comparator)`: This method is used to sort a given array of a type `T` and it also takes an instance of a `Comparator` interface. The `Comparator` provides rules to compare the object of the type `T`. Internally, it calls the `mergeSort()` method which sorts the array in ascending order.

`public static<T extends Comparable<T>> void sort(T []a,int order)`: This method is used to sort a given array of a type `T` which should implement the `Comparable` interface. It also contains an `order` as its parameter which is used to provide the order in which sorting needs to be done. If the provided value to the order doesnâ€™t match with the flags set in the method, it will throw an `UnsupportedOperationException`.

`public static<T> void sort(T []a,int order, Comparator<? super T>comparator)`: Works same as the previous discussed method. It also takes an instance of a `Comparator` interface which provides rules to compare the object of the type `T`.

All these `sort()` methods, perform the same functionality. There are two modes of the Merge Sort methods used in the above class.

`mergeSort()`: The `mergeSort()` is the recursive method which is used to divide the given array into different sub-arrays. Both of the Java Merge sort methods are in two overloaded forms one of which only has an array of type `T` and a temp array of type `T` as its parameter. This method uses the `Comparable` interface which is implemented by the class `T` to compare the objects of the type `T`. The other method passes the `Comparator` object which defines the rule of comparison between the objects of the type `T`.

`mergeAsc()`: Used to sort and merge arrays or sub-arrays in ascending order.
`mergeDesc()`:Used to sort and merge arrays or sub-arrays in descending order.

Employee.java

 01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849 `package` `com.javacodegeeks.entity;` `public` `class` `Employee ``implements` `Comparable{` `    ``private` `String firstName;``    ``private` `String lastName;``    ``private` `int` `emplyeeCode;``    ` `    ``public` `Employee(String fistName,String lastName,``int` `emplyeeCode){``        ``this``.firstName = fistName;``        ``this``.lastName = lastName;``        ``this``.emplyeeCode = emplyeeCode;``    ``}``    ` `    ``public` `String getFirstName() {``        ``return` `firstName;``    ``}``    ``public` `void` `setFirstName(String firstName) {``        ``this``.firstName = firstName;``    ``}``    ``public` `String getLastName() {``        ``return` `lastName;``    ``}``    ``public` `void` `setLastName(String lastName) {``        ``this``.lastName = lastName;``    ``}``    ``public` `int` `getEmplyeeCode() {``        ``return` `emplyeeCode;``    ``}` `    ``public` `void` `setEmplyeeCode(``int` `emplyeeCode) {``        ``this``.emplyeeCode = emplyeeCode;``    ``}` `    ``public` `String toString(){``        ``return` `"Employee Code: "``+getEmplyeeCode()+``", Name:"``+getFirstName()+``" "``+getLastName();``    ``}` `    ``public` `int` `compareTo(Employee o) {``        ``Employee e = (Employee)o;``        ``if``(``this``.emplyeeCode > e.getEmplyeeCode())``            ``return` `1``;``        ``if``(``this``.emplyeeCode < e.getEmplyeeCode())``            ``return` `-``1``;``        ``if``(``this``.emplyeeCode == e.getEmplyeeCode())``            ``return` `0``;``        ``return` `0``;``    ``}``}`

We have created an `Employee` class which implements the `Comparable` interface and overrides the `compareTo()` method. The comparison between the `Employee` objects is defined by comparing the `employeeCode` property of the `Employee` objects. The `comparTo()` method returns an integer, which tells whether the current `employeeCode` is greater than, or smaller than or equal to the compared `employeeCode`. It returns 1, if the current `employeeCode` is greater than the compared `employeeCode`, -1 if, the current `employeeCode` is smaller than the compared `employeeCode`, else it returns 0 if both are equal. Since, the `employeeCode` is of type integer, we have compared it using the simple integer comparison operators.

EmployeeFirstNameComparatorImpl.java

 01020304050607080910111213141516171819 ` ``package` `com.javacodegeeks.entity;` `import` `java.util.Comparator;` `public` `class` `EmployeeFirstNameComparatorImpl ``implements` `Comparator{` `    ``@Override``    ``public` `int` `compare(Employee o1, Employee o2) {``        ``if``(o1.getFirstName().compareTo(o2.getFirstName()) > ``0``){``            ``return` `1``;``        ``}``else` `if``(o1.getFirstName().compareTo(o2.getFirstName()) < ``0``){``            ``return` `-``1``;``        ``}``else``{``            ``return` `0``;``        ``}` `    ``}` `}`

The class implements the `Comparator` interface of the type `Employee` and provides the comparison rules by overriding the `compare()` method. The `compare()` method takes two arguments of the type `Employee` and:-
`return 1`: if `o1.getFirstName()` is greater than `o2.getFirstName()`.
`return -1`: if `o1.getFirstName()` is smaller than `o2.getFirstName()`.
`return 0`: if `o1.getFirstName()` is equals to `o2.getFirstName()`.

Please note that the method `getFirstName()` returns `String` which implements the `Comparable` interface. We have used the `compareTo()` method of the `String` class to compare the strings.

EmployeeLastNameComparatorImpl.java

 010203040506070809101112131415161718 ` ``package` `com.javacodegeeks.entity;` `import` `java.util.Comparator;` `public` `class` `EmployeeLastNameComparatorImpl ``implements` `Comparator {` `    ``@Override``    ``public` `int` `compare(Employee o1, Employee o2) {``        ``if``(o1.getLastName().compareTo(o2.getLastName()) > ``0``){``            ``return` `1``;``        ``}``else` `if``(o1.getLastName().compareTo(o2.getLastName()) < ``0``){``            ``return` `-``1``;``        ``}``else``{``            ``return` `0``;``        ``}` `    ``}``}`

This class works the same as the above class. But this class compares the objects on the basis of the `lastName` property of the `Employee` class. The `compare()` method takes two arguments of the type `Employee `and:-
`return 1`: if `o1.getLastName()` is greater than `o2.getLastName()`.
`return -1`: if `o1.getLastName()` is smaller than `o2.getLastName()`.
`return 0`: if `o1.getLastName()` is equals to `o2.getLastName()`.

MergesortObjectExample.java

 01020304050607080910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970 `package` `com.javacodegeeks.sorting.mergesort;` `import` `com.javacodegeeks.entity.Employee;``import` `com.javacodegeeks.entity.EmployeeFirstNameComparatorImpl;``import` `com.javacodegeeks.entity.EmployeeLastNameComparatorImpl;``import` `com.javacodegeeks.sorting.utility.SortingUtility;` `public` `class` `MergesortObjectExample {` `    ``/**``     ``* @param args``     ``*/``    ``public` `static` `void` `main(String[] args) {``        ``Employee []employees = ``new` `Employee[``5``];``        ``Employee employee = ``new` `Employee(``"John"``,``"Carter"``,``5658``);``        ``employees[``0``] = employee;``        ``employee = ``new` `Employee(``"Mary"``,``"Carter"``,``7412``);``        ``employees[``1``] = employee;``        ``employee = ``new` `Employee(``"Alex"``,``"Lumb"``,``1158``);``        ``employees[``2``] = employee;``        ``employee = ``new` `Employee(``"David"``,``"Jhonson"``,``1254``);``        ``employees[``3``] = employee;``        ``employee = ``new` `Employee(``"Shaun"``,``"Smith"``,``4587``);``        ``employees[``4``] = employee;` `        ``System.out.println(``"Sorting in ascending order on basis of employeeCode...\n"``);``        ``printArray(employees);``        ``SortingUtility.sort(employees);``        ``System.out.println(``"After sorting..."``);``        ``printArray(employees);` `        ``System.out.println(``"\nSorting in ascending order on basis of employeeFirstName...\n"``);``        ``printArray(employees);``        ``SortingUtility.sort(employees,``new` `EmployeeFirstNameComparatorImpl());``        ``System.out.println(``"After sorting..."``);``        ``printArray(employees);` `        ``System.out.println(``"\nSorting in ascending order on basis of employeeLastName...\n"``);``        ``printArray(employees);``        ``SortingUtility.sort(employees,``new` `EmployeeLastNameComparatorImpl());``        ``System.out.println(``"After sorting..."``);``        ``printArray(employees);` `        ``System.out.println(``"\nSorting in descending order on basis of employeeCode...\n"``);``        ``printArray(employees);``        ``SortingUtility.sort(employees,SortingUtility.DESC_ORDER);``        ``System.out.println(``"After sorting..."``);``        ``printArray(employees);` `        ``System.out.println(``"\nSorting in descending order on basis of employeeFirstName...\n"``);``        ``printArray(employees);``        ``SortingUtility.sort(employees,SortingUtility.DESC_ORDER,``new` `EmployeeFirstNameComparatorImpl());``        ``System.out.println(``"After sorting..."``);``        ``printArray(employees);` `        ``System.out.println(``"\nSorting in descending order on basis of employeeLastName...\n"``);``        ``printArray(employees);``        ``SortingUtility.sort(employees,SortingUtility.DESC_ORDER,``new` `EmployeeLastNameComparatorImpl());``        ``System.out.println(``"After sorting..."``);``        ``printArray(employees);` `    ``}` `    ``public` `static`` ``void` `printArray(T []a){``        ``for``(T t : a){``            ``System.out.println(t);``        ``}``    ``}` `}`

If we run the above code, we will have the following results:

 0102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 `Sorting ``in` `ascending order on basis of employeeCode...` `Employee Code: 5658, Name:John Carter``Employee Code: 7412, Name:Mary Carter``Employee Code: 1158, Name:Alex Lumb``Employee Code: 1254, Name:David Jhonson``Employee Code: 4587, Name:Shaun Smith``After sorting...``Employee Code: 1158, Name:Alex Lumb``Employee Code: 1254, Name:David Jhonson``Employee Code: 4587, Name:Shaun Smith``Employee Code: 5658, Name:John Carter``Employee Code: 7412, Name:Mary Carter` `Sorting ``in` `ascending order on basis of employeeFirstName...` `Employee Code: 1158, Name:Alex Lumb``Employee Code: 1254, Name:David Jhonson``Employee Code: 4587, Name:Shaun Smith``Employee Code: 5658, Name:John Carter``Employee Code: 7412, Name:Mary Carter``After sorting...``Employee Code: 1158, Name:Alex Lumb``Employee Code: 1254, Name:David Jhonson``Employee Code: 5658, Name:John Carter``Employee Code: 7412, Name:Mary Carter``Employee Code: 4587, Name:Shaun Smith` `Sorting ``in` `ascending order on basis of employeeLastName...` `Employee Code: 1158, Name:Alex Lumb``Employee Code: 1254, Name:David Jhonson``Employee Code: 5658, Name:John Carter``Employee Code: 7412, Name:Mary Carter``Employee Code: 4587, Name:Shaun Smith``After sorting...``Employee Code: 7412, Name:Mary Carter``Employee Code: 5658, Name:John Carter``Employee Code: 1254, Name:David Jhonson``Employee Code: 1158, Name:Alex Lumb``Employee Code: 4587, Name:Shaun Smith` `Sorting ``in` `descending order on basis of employeeCode...` `Employee Code: 7412, Name:Mary Carter``Employee Code: 5658, Name:John Carter``Employee Code: 1254, Name:David Jhonson``Employee Code: 1158, Name:Alex Lumb``Employee Code: 4587, Name:Shaun Smith``After sorting...``Employee Code: 7412, Name:Mary Carter``Employee Code: 5658, Name:John Carter``Employee Code: 4587, Name:Shaun Smith``Employee Code: 1254, Name:David Jhonson``Employee Code: 1158, Name:Alex Lumb` `Sorting ``in` `descending order on basis of employeeFirstName...` `Employee Code: 7412, Name:Mary Carter``Employee Code: 5658, Name:John Carter``Employee Code: 4587, Name:Shaun Smith``Employee Code: 1254, Name:David Jhonson``Employee Code: 1158, Name:Alex Lumb``After sorting...``Employee Code: 4587, Name:Shaun Smith``Employee Code: 7412, Name:Mary Carter``Employee Code: 5658, Name:John Carter``Employee Code: 1254, Name:David Jhonson``Employee Code: 1158, Name:Alex Lumb` `Sorting ``in` `descending order on basis of employeeLastName...` `Employee Code: 4587, Name:Shaun Smith``Employee Code: 7412, Name:Mary Carter``Employee Code: 5658, Name:John Carter``Employee Code: 1254, Name:David Jhonson``Employee Code: 1158, Name:Alex Lumb``After sorting...``Employee Code: 4587, Name:Shaun Smith``Employee Code: 1158, Name:Alex Lumb``Employee Code: 1254, Name:David Jhonson``Employee Code: 5658, Name:John Carter``Employee Code: 7412, Name:Mary Carter`

7. Summary

In this article we discussed the merge sort algorithm in Java. Mergesort is good for slowly accessed data. Like a linked list which is random-accessed. The strategy behind this algorithm is that it first splits up the array elements in to smallest possible arrays. Then the arrays are merged and sorted.

The merging is done by combining two already sorted arrays into one empty array and we implemented an example regarding this. We also implemented an example regarding the sorting of the Mergesort by dividing an array into two sub-arrays, sort each of them, and then merge them into one.

Finally, we discussed the sorting in descending order using this algorithm and how to sort objects of any type using the Mergesort.

This was a code example on Merge Sort Java algorithm.

You can download the source code of this example from here: Merge Sort Java algorithm – Code Example

Last updated on Jan. 23rd, 2020

Rohit Joshi

Rohit Joshi works as a Software Engineer in the Consumer Product Sector. He is a Sun Certified Java Programmer. He had worked in projects related to different domains. He is also involved in system analysis and system designing. He mainly works in Core Java and J2EE technologies but also have good experience in front-end technologies like Javascript and Jquery.
Subscribe
Notify of

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

1 Comment
Inline Feedbacks
srujana pasula
3 years ago

`for`

`(`

`int`

`i=`

`0`

`;i<size;i++){`
`            `

`item = (`

`int`

`)(Math.random()*`

`100`

`); `
`            `

`array[i] = item;`
`can you explain this code `