简言

归并排序是一种分治算法，它将一个大的数组分成两个较小的数组，分别对它们进行排序，然后将这两个已排序的数组归并成一个有序的数组。

Java实现一

public class MyMergeSort {

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int leftIndex = 0;
        int rightIndex = 0;
        int resultIndex = 0;
        // 排序
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                result[resultIndex] = left[leftIndex];
                leftIndex++;
            } else {
                result[resultIndex] = right[rightIndex];
                rightIndex++;
            }
            resultIndex++;
        }
        // 如果左边还有剩余，直接放到结果数组中
        if (leftIndex < left.length) {
            System.arraycopy(left, leftIndex, result, resultIndex, left.length - leftIndex);
        }
        // 如果右边还有剩余，直接放到结果数组中
        if (rightIndex < right.length) {
            System.arraycopy(right, rightIndex, result, resultIndex, right.length - rightIndex);
        }
        return result;
    }

    private static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int mid = arr.length / 2;
        // 分治，分成两个数组
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        // 归并
        return merge(sort(left), sort(right));
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 9, 2, 8, 7, 6, 4};
        int[] result = sort(arr);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }

}

Java实现二

不需要额外创建空间

public class MergeSort {
    private static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[m + 1 + j];
        }

        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    private static void sort(int[] arr, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

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

    public static void main(String[] args) {
        int[] arr = {3, 5, 1, 9, 2, 8, 7, 6, 4};
        sort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

golang实现

package main

import "fmt"

func main() {
	arr := []int{5, 3, 8, 6, 2, 7, 1, 4}
	fmt.Println("Original array:", arr)
	sortedArr := mergeSort(arr)
	fmt.Println("Sorted array:", sortedArr)
}

// 合并排序
func mergeSort(arr []int) []int {
	// 如果长度小于等于1则返回
	if len(arr) <= 1 {
		return arr
	}
	// 迭代，每次划分数组左右两边进行排序
	mid := len(arr) >> 1
	left := mergeSort(arr[:mid])
	right := mergeSort(arr[mid:])
	return merge(left, right)
}

// 合并
func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	l, r := 0, 0
	for l < len(left) && r < len(right) {
		if left[l] <= right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	// 还有一些剩余元素需要补充上去
	if l < len(left) {
		result = append(result, left[l:]...)
	}
	if r < len(right) {
		result = append(result, right[r:]...)
	}
	return result
}

在这个程序中，mergeSort函数是主要的排序函数，它首先检查数组的长度，如果长度小于或等于1，那么数组已经是有序的，直接返回。否则，将数组分为两半，对每半进行归并排序，然后使用merge函数将两个已排序的数组合并。merge函数会将两个有序的数组合并为一个有序的数组。最后，在main函数中，我们创建一个初始的无序数组，调用mergeSort函数进行排序，然后打印排序后的数组。