In this tutorial, I will be with you to learn about an algorithm to sort the elements in an array, Merge Sort algorithm!
OK,
Now suppose I have an array of numeric values arranged as follows:
|
1 |
Integer[] array = { 1, 23, 4, 5, 100, 54 }; |
The Merge Sort algorithm divides the array into multiple child arrays, until each of the children has only one element. Then, it compares the values of the sub arrays so that they are grouped together into sorted arrays. And finally, we will get a sorted array.
In our example, using the Merge Sort algorithm, the following steps will occur:
Step 1: Divide the large array into two sub-arrays:
|
1 |
1 23 4 _ 5 100 54 |
- Step 2: Continue to split
|
1 |
1 _ 23 4 _ 5 _ 100 54 |
- Step 3: Still have the array containing more than 2 elements so continue to split
|
1 |
1 _ 23 _ 4 _ 5 _ 100 _ 54 |
- Step 4: Because all the arrays now contain one element, we now compare the values and collect them.
|
1 |
1 _ 4 23 _ 5 _ 54 100 |
- Step 5: Continue collecting:
|
1 |
1 4 23 _ 5 54 100 |
- Result:
|
1 |
1 4 5 23 54 100 |
As you see, after a few steps divided, the array was rearranged.
The idea is that, so what is the Merge Sort algorithm? Let me tell you the following.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Start MergeSort algorithm MergeSort( array has n elements ) if ( n < 2 ) return array // Split declare subArrayFirst variable as an array = array[0] ... array[n/2] declare subArrayLast variable as an array = array[n/2+1] ... array[n] // Call recursively to sort arrays declare sortedSubArrayFirst variable = MergeSort( subArrayFirst ) declare sortedSubArraySecond variable = MergeSort( subArrayLast ) // Collect return Merge( sortedSubArrayFirst, sortedSubArraySecond ) End MergeSort algorithm |
The Merge algorithm looks like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Start Merge algorithm Merge( subArrayFirst variable is an array, subArrayLast variable is an array ) declare n variable = number of elements of subArrayFirst array + number of elements of subArrayLast array; declare sortedArray variable with number of elements as n declare i variable = 0 declare j variable = 0 for (declare k variable = 0; k < n; k++) { if j < number of elements of subArrayLast array or (i less than number of elements of subArrayFirst array and element at i index in subArrayFirst array less than element at j index in subArrayLast array) sortedArray[k] = subArrayFirst[i] increase value of i variable into 1 otherwise sortedArray[k] = subArrayLast[j] increase value of j variable into 1 } End Merge algorithm |
OK, here’s how to implement the Merge Sort algorithm with the Java language:
|
1 2 3 4 5 6 7 8 9 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 |
package com.huongdanjava.mergesort; import java.lang.reflect.Array; import java.util.Arrays; import java.util.Comparator; public class MergeSort { public <K> K[] doMergeSort(K[] arrayNeedToSort, Comparator<K> comparator) { int n = arrayNeedToSort.length; if (n < 2) { return arrayNeedToSort; } int middle = n / 2; K[] subArrayFirst = Arrays.copyOfRange(arrayNeedToSort, 0, middle); K[] sortedSubArrayFirst = doMergeSort(subArrayFirst, comparator); K[] subArrayLast = Arrays.copyOfRange(arrayNeedToSort, middle, n); K[] sortedSubArraySecond = doMergeSort(subArrayLast, comparator); return merge(sortedSubArrayFirst, sortedSubArraySecond, comparator); } private <K> K[] merge(K[] sortedSubArrayFirst, K[] sortedSubArraySecond, Comparator<K> comparator) { int n = sortedSubArrayFirst.length + sortedSubArraySecond.length; K[] sortedArray = (K[]) Array.newInstance(sortedSubArrayFirst[0].getClass(), n); int i = 0; int j = 0; for (int k = 0; k < n; k++) { if (j == sortedSubArraySecond.length || (i < sortedSubArrayFirst.length && comparator.compare(sortedSubArrayFirst[i], sortedSubArraySecond[j]) < 1)) { sortedArray[k] = sortedSubArrayFirst[i++]; } else { sortedArray[k] = sortedSubArraySecond[j++]; } } return sortedArray; } } |
In this implementation of the Merge Sort algorithm, I used the Comparator interface to compare two objects of the same class.
Below, I will use the code above to make an example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package com.huongdanjava.mergesort; import java.util.Comparator; public class TestMergeSort { public static void main(String args[]) { MergeSort mergeSort = new MergeSort(); Integer[] array = {1, 23, 4, 5, 100, 54}; Comparator<Integer> comparator = new Comparator<Integer>() { public int compare(Integer o1, Integer o2) { if (o1 > o2) return 1; else if (o1 == o2) return 0; else return -1; } }; Integer[] sortedArray = mergeSort.doMergeSort(array, comparator); for (Integer o : sortedArray) { System.err.println(o.intValue()); } } } |
Result:
