2024拼多多校招面试真题汇总及其解答（二）

6. 【算法题】归并排序

归并排序（Merge Sort）是一种分治算法，它将待排序的序列递归地分成两个子序列，然后将两个有序的子序列合并成一个有序的序列。

归并排序的算法流程如下：

1. 递归地将待排序的序列分成两个子序列，直到每个子序列只有一个元素。
2. 将两个有序的子序列合并成一个有序的序列。

归并排序的代码实现如下：

// 归并排序
public static void mergeSort(int[] arr) {if (arr.length <= 1) {return;}// 将待排序的序列分成两个子序列int mid = arr.length / 2;int[] left = Arrays.copyOfRange(arr, 0, mid);int[] right = Arrays.copyOfRange(arr, mid, arr.length);// 递归地排序两个子序列mergeSort(left);mergeSort(right);// 将两个有序的子序列合并成一个有序的序列merge(left, right, arr);
}// 合并两个有序的子序列
private static void merge(int[] left, int[] right, int[] arr) {int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] < right[j]) {arr[k++] = left[i++];} else {