归并排序（Merge Sort）是一种典型的分治算法，它将一个大问题分解成多个小问题，逐步解决，再合并结果，最终得到排序后的序列。

归并排序的思路：

1. 分解（Divide）：将待排序的数组分成两半，递归地对这两半分别进行归并排序。
2. 解决（Conquer）：对分解出的子数组继续进行排序，直到每个子数组只有一个元素（因为一个元素自然是有序的）。
3. 合并（Combine）：将排序后的子数组合并成一个有序的大数组。合并是归并排序的核心步骤。

归并排序的时间复杂度与空间复杂度：

1. 时间复杂度：
   • 归并排序的时间复杂度是 O(nlogn)，无论是最坏情况、最佳情况还是平均情况。这里的 n 是待排序元素的数量，logn 是因为每次递归将数组分成两半，直到数组大小为1。
   • 每一层递归的合并操作是线性时间复杂度O(n)，递归深度是logn，所以总的时间复杂度是 O(nlogn)。
2. 空间复杂度：
   • 归并排序需要额外的空间来存储合并过程中的中间结果，空间复杂度为O(n)。
   • 在递归调用过程中，每次递归调用栈的深度是logn，但归并过程中需要额外的存储空间来存储中间的合并结果，所以总空间复杂度是O(n)。

归并排序的Java实现：

public class MergeSort {
    
    // 归并排序函数
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 调用辅助函数进行递归排序
        mergeSortHelper(arr, 0, arr.length - 1);
    }

    // 递归的归并排序方法
    private static void mergeSortHelper(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;  // 防止溢出
            mergeSortHelper(arr, left, mid);       // 排序左半部分
            mergeSortHelper(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++];
            }
        }

        // 如果左半部分有剩余元素，直接复制到temp数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 如果右半部分有剩余元素，直接复制到temp数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将临时数组的内容拷贝回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    // 测试归并排序
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前: ");
        printArray(arr);

        mergeSort(arr);

        System.out.println("排序后: ");
        printArray(arr);
    }

    // 打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

代码解析：

1. mergeSort 函数：是外部调用的接口，接收待排序的数组。首先检查数组的有效性（如果为空或长度小于2直接返回）。
2. mergeSortHelper 函数：是递归的核心部分，负责将数组分成两部分，分别递归排序，直到分割到只有一个元素为止。
3. merge 函数：这是合并的关键部分，它接受三个参数：left, mid, right，分别表示左部分的起始索引，右部分的结束索引。合并操作会创建一个临时数组，按顺序将两个已排序的子数组合并到这个临时数组中，然后再将其复制回原数组。
4. printArray 函数：打印数组元素的辅助函数。

测试：

给定输入数组 {38, 27, 43, 3, 9, 82, 10}，归并排序后的输出应为：

排序前:  38 27 43 3 9 82 10  
排序后:  3 9 10 27 38 43 82