Core Java

Merge Sort Java algorithm – Code Example

Photo of Rohit Joshi Rohit JoshiJuly 9th, 2014Last Updated: July 5th, 2022
1 493 21 minutes read

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 read more about Insertion Sort and Quicksort Java algorithms.

You can also check this tutorial in the following video:

Merge Sort Java Algorithm Code Example – 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.

Merge Sort Java - diagram
Mergesort algorithm diagram

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.

Merge Sort Java - compare and merge
compare and merge

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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:

1
2
3
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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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<totalItems;i++){
            a[lowerIndexCursor+i] = tempArray[i];
        }
    }
     
    public static void printArray(int []array){
        for(int i : array){
            System.out.print(i+" ");
        }
    }
     
    public static int[] getArray(){
        int size=10;
        int []array = new int[size];
        int item = 0;
        for(int i=0;i<size;i++){
            item = (int)(Math.random()*100);
            array[i] = item;
        }
        return array;
    }
 
}

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

1
2
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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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<totalItems;i++){
            a[lowerIndexCursor+i] = tempArray[i];
        }
    }
 
    public static void printArray(int []array){
        for(int i : array){
            System.out.print(i+" ");
        }
    }
 
    public static int[] getArray(){
        int size=10;
        int []array = new int[size];
        int item = 0;
        for(int i=0;i<size;i++){
            item = (int)(Math.random()*100);
            array[i] = item;
        }
        return array;
    }
 
}

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

1
2
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

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
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<T extends Comparable<T>> void sort(T []a){
        mergeSort(a,0, a.length-1, ASC_ORDER);
    }
 
    public static<T> void sort(T []a, Comparator<? super T>comparator){
        mergeSort(a,0, a.length-1, ASC_ORDER,comparator);
    }
 
    public static<T extends Comparable<T>> void sort(T []a,int order){
        mergeSort(a,0, a.length-1, order);
    }
 
    public static<T> void sort(T []a,int order, Comparator<? super T>comparator){
        mergeSort(a,0, a.length-1, order,comparator);
    }
 
    public static<T extends Comparable<T>> 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<T> void mergeSort(T []a,int lowerIndex,int upperIndex,int order, Comparator<? super T>comparator){
        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<T extends Comparable<T>> 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<T>)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<totalItems;i++){
            a[lowerIndexCursor+i] = (T) tempArray[i];
        }
    }
 
 
    @SuppressWarnings("unchecked")
    public static<T> void mergeAsc(T []a,int lowerIndexCursor,int higerIndex,int upperIndex,Comparator<? super T>comparator){
        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<totalItems;i++){
            a[lowerIndexCursor+i] = (T) tempArray[i];
        }
    }
 
    @SuppressWarnings("unchecked")
    public static<T extends Comparable<T>> 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<T>)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<totalItems;i++){
            a[lowerIndexCursor+i] = (T) tempArray[i];
        }
    }
 
 
    @SuppressWarnings("unchecked")
    public static<T> void mergeDesc(T []a,int lowerIndexCursor,int higerIndex,int upperIndex,Comparator<? super T>comparator){
        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<totalItems;i++){
            a[lowerIndexCursor+i] = (T) tempArray[i];
        }
    }
 
    private static Object[] getTempArray(int length){
        Object []tempArray = new Object[length];
        return tempArray;
    }
}

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package com.javacodegeeks.entity;
 
public class Employee implements Comparable<Employee>{
 
    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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
 package com.javacodegeeks.entity;
 
import java.util.Comparator;
 
public class EmployeeFirstNameComparatorImpl implements Comparator<Employee>{
 
    @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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
 package com.javacodegeeks.entity;
 
import java.util.Comparator;
 
public class EmployeeLastNameComparatorImpl implements Comparator<Employee> {
 
    @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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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<T> void printArray(T []a){
        for(T t : a){
            System.out.println(t);
        }
    }
 
}

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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.

8. Download the source code

This was a code example on Merge Sort Java algorithm.

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

Last updated on Jan. 23rd, 2020

Photo of Rohit Joshi Rohit JoshiJuly 9th, 2014Last Updated: July 5th, 2022
1 493 21 minutes read
Photo of Rohit Joshi

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
guest

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

1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
srujana pasula
srujana pasula
4 years ago

for

(

int

i=

0

;i<size;i++){
            

item = (

int

)(Math.random()*

100

);
            

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

0
Reply
Back to top button