## 1.绪论

In this tutorial, we’ll have a look at the Merge Sort algorithm and its implementation in Java.

Merge sort is one of the most efficient sorting techniques, and it’s based on the “divide and conquer” paradigm.

## 2.算法

Merge sort is a “divide and conquer” algorithm, wherein we first divide the problem into subproblems. When the solutions for the subproblems are ready, we combine them together to get the final solution to the problem.

We can easily implement this algorithm using recursion, as we deal with the subproblems rather than the main problem.

We can describe the algorithm as the following 2 step process:

• Divide: In this step, we divide the input array into 2 halves, the pivot being the midpoint of the array. This step is carried out recursively for all the half arrays until there are no more half arrays to divide.
• Conquer: In this step, we sort and merge the divided arrays from bottom to top and get the sorted array.

The following diagram shows the complete merge sort process for an example array {10, 6, 8, 5, 7, 3, 4}.

If we take a closer look at the diagram, we can see that the array is recursively divided into two halves until the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back while sorting: ## 3.实施

For the implementation, we’ll write a mergeSort function that takes in the input array and its length as the parameters. This will be a recursive function, so we need the base and the recursive conditions.

The base condition checks if the array length is 1 and it will just return. For the rest of the cases, the recursive call will be executed.

For the recursive case, we get the middle index and create two temporary arrays, l[] and r[]. Then we call the mergeSort function recursively for both the sub-arrays:

``````public static void mergeSort(int[] a, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] l = new int[mid];
int[] r = new int[n - mid];

for (int i = 0; i < mid; i++) {
l[i] = a[i];
}
for (int i = mid; i < n; i++) {
r[i - mid] = a[i];
}
mergeSort(l, mid);
mergeSort(r, n - mid);

merge(a, l, r, mid, n - mid);
}``````

Next, we call the merge function, which takes in the input and both the sub-arrays, as well as the start and end indices of both the sub arrays.

The merge function compares the elements of both sub-arrays one by one and places the smaller element into the input array.

merge函数逐一比较两个子数组的元素，并将较小的元素放入输入数组。

When we reach the end of one of the sub-arrays, the rest of the elements from the other array are copied into the input array, thereby giving us the final sorted array:

``````public static void merge(
int[] a, int[] l, int[] r, int left, int right) {

int i = 0, j = 0, k = 0;
while (i < left && j < right) {
if (l[i] <= r[j]) {
a[k++] = l[i++];
}
else {
a[k++] = r[j++];
}
}
while (i < left) {
a[k++] = l[i++];
}
while (j < right) {
a[k++] = r[j++];
}
}
``````

The unit test for the program is:

``````@Test
public void positiveTest() {
int[] actual = { 5, 1, 6, 2, 3, 4 };
int[] expected = { 1, 2, 3, 4, 5, 6 };
MergeSort.mergeSort(actual, actual.length);
assertArrayEquals(expected, actual);
}``````

## 4.复杂性

As merge sort is a recursive algorithm, the time complexity can be expressed as the following recursive relation:

``T(n) = 2T(n/2) + O(n)``

2T(n/2) corresponds to the time required to sort the sub-arrays, and O(n) is the time to merge the entire array.

2T(n/2)对应于排序子数组所需的时间，而O(n)是合并整个数组的时间。

When solved, the time complexity will come to O(nLogn).

This is true for the worst, average, and best cases, since it’ll always divide the array into two and then merge.

The space complexity of the algorithm is O(n), as we’re creating temporary arrays in every recursive call.

## 5.总结

In this brief article, we explored the merge sort algorithm and how we can implement it in Java.

The entire working code is available over on GitHub.  