用 java语言以测试驱动开发实现归并排序

以下是用 Java 语言以测试驱动开发实现归并排序的代码：

MergeSort.java

public class MergeSort {
    public static void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        for (i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }
}

MergeSortTest.java

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class MergeSortTest {
    @Test
    public void testSort() {
        int[] arr = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
        int[] expected = { 1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9 };
        MergeSort.sort(arr);
        assertArrayEquals(expected, arr);
    }
}

在 MergeSort 类中，我们实现了归并排序算法。它接收一个整数数组 `arr`，并对其进行排序。它使用递归方法 `mergeSort()`，将数组不断分成两半，直到每半只剩下一个元素。然后，它合并这两个有序数组，使用 `merge()` 方法。`merge()` 方法将两个有序数组合并成一个有序数组。它使用一个临时数组 `temp`，将两个数组中较小的元素依次放入其中。最后，将 `temp` 中的元素复制回原数组。

在 MergeSortTest 类中，我们编写了一个测试方法 `testSort()`，用于测试归并排序算法是否正确。它创建一个整数数组 `arr`，并调用 `MergeSort.sort()` 方法对其进行排序。然后，我们断言排序后的数组与期望的数组 `expected` 相等。如果归并排序算法实现正确，测试方法将通过。