归并排序

归并排序是一种分治算法。它将输入数组分成两半，对这两半递归调用自身，然后将两个已排序的半部分合并。merge() 函数用于合并两个半部分。merge(arr, l, m, r) 是关键过程，它假设 arr[l..m] 和 arr[m+1..r] 已经排序，并将这两个已排序的子数组合并成一个。