Merge Sort in Java – 在Java中合并排序

最后修改: 2018年 9月 30日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.绪论

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

在本教程中，我们将了解一下合并排序算法及其在Java中的实现。

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

合并排序是最有效的排序技术之一，它基于“分而治之 “范式。

2. The Algorithm

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}.

下图显示了一个例子数组{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:

如果我们仔细看看这个图，我们可以看到数组被递归地分成两半，直到大小变成1。一旦大小变成1，合并过程就开始行动，在排序的同时开始将数组合并回来。

mergesort1

3. Implementation

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.

在实现上，我们将写一个mergeSort函数，将输入数组及其长度作为参数。这将是一个递归函数，所以我们需要基数和递归条件。

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.

基本条件检查数组长度是否为1，它将直接返回。对于其余的情况，将执行递归调用。

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:

对于递归情况，我们得到中间索引并创建两个临时数组，l[]和r[]。然后我们为两个子数组递归地调用mergeSort函数。

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.

接下来，我们调用merge函数，它接收输入和两个子数组，以及两个子数组的开始和结束索引。

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. Complexity

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).

当解决时，时间复杂性将达到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.

该算法的空间复杂度为O(n),，因为我们在每次递归调用中都会创建临时数组。

5. Conclusion

5.总结

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

在这篇简短的文章中，我们探讨了合并排序算法以及我们如何在Java中实现它。

The entire working code is available over on GitHub.

整个工作代码可在GitHub上获得，。