何时使用归并排序

• 当数据结构不支持随机访问时使用合并排序，因为它适用于纯顺序访问（前向迭代器，而不是随机访问迭代器）。它也广泛用于外部排序，与顺序访问相比，随机访问可能非常非常昂贵。独立使用，将每个文件写入一个文件，然后对生成的文件进行合并排序。
• 此外，我们可以在需要稳定排序时使用归并排序。这是归并排序非常重要的特性。
• 处理链表时，合并排序更快。这是因为在合并列表时可以轻松更改指针。它只需要通过列表一次 (O(n))。
• 如果发生大量并行化，那么并行化合并排序比其他排序算法更简单。

归并排序是一种分而治之的算法。
分治算法将原始数据分成更小的数据集来解决问题。

在合并排序过程中，集合中的对象被分成两个集合。
要拆分集合，Mergesort 将取集合的中间部分，并将集合拆分为左侧和右侧部分。
生成的集合再次通过 Mergesort 算法递归拆分，直到它们被分解为每个集合中的单个元素。

拆分每个集合后，归并排序算法开始合并通过上述过程获得的所有集合。
合并两个集合 Mergesort 在每个集合的开头开始。
它选择较小的对象并将该对象插入到新集合中。
对于这个集合，它现在选择下一个元素，并通过一次比较每个集合中的一个元素从两个集合中选择较小的元素。

此过程创建一个已排序元素的集合（需要排序的所有元素的子集）。
对第一步中获得的所有可用集合递归完成此过程，例如：拆分集合。

一旦两个集合中的所有元素都插入到新集合中，Mergesort 就成功地对集合进行了排序。

为避免创建过多集合，通常只创建一个新集合，并将新集合和现有集合视为不同的集合。

Java实现合并排序示例

在下面的示例中，我们以富有表现力的方式实现了归并排序算法，使其更易于理解。
按照下面给定的合并排序代码中每个步骤/语句上方的注释进行操作。

import java.util.*;
public class MergerSort 
{
	public static void main(String[] args) 
	{
		// 未排序的数组
		Integer[] a = { 2, 6, 3, 5, 1 };

		// 调用mergeSort，实现合并排序
		mergeSort(a);

		// 查看排序后的数组
		System.out.println(Arrays.toString(a));
	}
	@SuppressWarnings("rawtypes") 
	public static Comparable[] mergeSort(Comparable[] list) 
	{
		// 检查列表是否为空
        if (list.length <= 1) {
            return list;
        }

        // 将数组分为两个集合
        Comparable[] first = new Comparable[list.length / 2];
        Comparable[] second = new Comparable[list.length - first.length];
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);

        // 两部分分别递归排序
        mergeSort(first);
        mergeSort(second);

        // 将结果合并
        merge(first, second, list);
        return list;
    }

	@SuppressWarnings({ "rawtypes", "unchecked" }) 
    private static void merge(Comparable[] first, Comparable[] second, Comparable[] result) 
	{
        // 第1个数组中的索引位置-从第一个元素开始
        int iFirst = 0;

        // 第2个数组中的索引位置-从第一个元素开始
        int iSecond = 0;

        // 合并数组中的索引位置-从第一个元素开始
        int iMerged = 0;

        // 比较两个数组中的元素
        // 把较小的移动到合并数组中
        while (iFirst < first.length && iSecond < second.length) 
        {
            if (first[iFirst].compareTo(second[iSecond]) < 0) 
            {
                result[iMerged] = first[iFirst];
                iFirst++;
            } 
            else 
            {
                result[iMerged] = second[iSecond];
                iSecond++;
            }
            iMerged++;
        }
        //复制两半部分的剩余元素-每半部分都有已排序的元素
        System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst);
        System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond);
    }
}

输出：

Input Array :  [ 2, 6, 3, 5, 1, 1, 8 ]
Output Array : [ 1, 1, 2, 3, 5, 6, 8 ]
Input Array :  [ 12, 16, 333, 50, 1000, 5, 897, 1, 3, 66, 13 ]
Output Array : [ 1, 3, 5, 12, 13, 16, 50, 66, 333, 897, 1000 ]