最近在研究大数据的分治思想，很多场景计算得出的中间结果都是“内部有序，外部无序”，这时候就要用到“归并排序”算法将多个这样的结果集合归并为一个有序的集合。于是就复习了一下“归并排序”。

归并排序的大概流程

用递归将数组拆分成一个个最小的数组

{6, 9, 5, 2, 4, 9, 3, 11, 44, 55, 43, 27, 18, 94, 35, 32, 17}
{6, 9, 5, 2, 4, 9, 3, 11, 44}{55, 43, 27, 18, 94, 35, 32, 17}
{6, 9, 5, 2, 4}{9, 3, 11, 44}{55, 43, 27, 18}{94, 35, 32, 17}
{6, 9, 5}{2, 4}{9, 3}{11, 44}{55, 43}{27, 18}{94, 35}{32, 17}
{6, 9}{5}{2}{4}{9}{3}{11}{44}{55}{43}{27}{18}{94}{35}{32}{17}
{6}{9}{5}{2}{4}{9}{3}{11}{44}{55}{43}{27}{18}{94}{35}{32}{17}

将小数组逐个排序合并

{6, 9}{5}{2}{4}{9}{3}{11}{44}{55}{43}{27}{18}{94}{35}{32}{17}
{5, 6, 9}{2, 4}{3, 9}{11, 44}{43, 55}{18, 27}{35, 94}{17, 32}
{2, 4, 5, 6, 9}{3, 9, 11, 44}{18, 27, 43, 55}{17, 32, 35, 94}
{2, 3, 4, 5, 6, 9, 9, 11, 44}{17, 18, 27, 32, 35, 43, 55, 94}
{2, 3, 4, 5, 6, 9, 9, 11, 17, 18, 27, 32, 35, 43, 44, 55, 94}

java代码实现

public class MergeSort {

    public static void main(String[] args) {
        int[] array = {6, 9, 5, 2, 4, 9, 3, 11, 44, 55, 43, 27, 18, 94, 35, 32, 17};
        sort(array, 0, array.length -1);
        Utils.printf(array);
    }


    private static void sort(int[] array, int begin, int end) {
        if(begin >= end ){
            return;
        }

        int mid = (begin + end) / 2;
        
        sort(array, begin, mid);
        sort(array, mid + 1, end);
        merge(array, begin, mid, end);
    }

    private static void merge(int[] array, int begin, int mid, int end) {

        //合并两个数组结果的临时数组
        int[] temp = new int[end - begin + 1];
        //左边数组的遍历指针
        int lStart = begin;
        //右边数组的遍历指针
        int rStart = mid + 1;
        int k = 0;
        while (lStart <= mid && rStart <= end){
            //两个数组的指针对应的元素做比较
            if(array[lStart] < array[rStart]){
                //如果左边的元素小，把左边的元素放入临时数组，并将左边指针向前移动
                temp[k ++] = array[lStart ++];
            }else {
                //如果右边的元素小，把右边的元素放入临时数组，并将右边指针向前移动
                temp[k ++] = array[rStart ++];
            }
        }

        //如果两个数组中还有剩余的元素，就全部加到临时数组中（剩余的肯定比之前加入的元素值大，无需比较）
        while (lStart <= mid){
            temp[k ++] = array[lStart ++];
        }
        while (rStart <= end){
            temp[k ++] = array[rStart ++];
        }
        //把排序合并后的临时数组覆盖到原数组中
        for(int i =0; i < temp.length; i ++){
            array[begin + i] = temp[i];
        }

    }

}

大数据的分布式计算中“归并排序”的应用场景

在大数据场景中，数据量远大于计算机的内存，磁盘和网络的IO又是无法解决的瓶颈，就需要用到分治思想。
比如有1000G的中国2020年某电商平台用户消费总金额数据。数据格式是用户名：消费总金额。所有数据都是无序的。现在有1台磁盘5T/内存8G（程序可用内存约为5G多）的计算机。如何将数据按消费总金额从大到小排序输出？

1. 计算机上将1000G的数据每次加载5G到内存中做排序（这一步不一定要用归并排序，可以用快排等其他排序方式）输出一个5G的小文件，这样得到200份内部有序外部无序的5G文件。

image.png

2. 从每个5G文件中读取25M数据到内存中，内存中有200个有序的数组。这个就要用到“多路归并”，创建一个有序队列，从200个数组每个读取一个元素放入有序队列。

a. 从有序队列中取出第一个元素。
b. 将此元素数据写入输出的文件中，并从此元素所属的数组中的下一个元素放入有序队列。
c. 重复步骤a，b直到某个数组元素耗尽，从这个数组所属的5G文件中，继续加载25M数据到内存中。
d. 重复步骤a，b，c直到所有5G文件的数据全部加载到内存中，并写入到输出文件。