# 256M的内存如何对16g的数组进行排序

参考 [256M的内存如何对16g的数组进行排序](https://youngzil.gitbook.io/notes/shu-ju-jie-gou-yu-suan-fa/suan-fa/256m-de-nei-cun-ru-he-dui-16g-de-shu-zu-jin-xing-pai-xu)

多路归并，因为没要求存储，只要求了内存，可以多路归并，加入每个元素都是 1M，则可以最多分成 256 组，然后进行归并。

具体描述：采用外部排序，先将16 g数组分成 256 M 一组，然后分别读入内存进行内部排序「比如说可以使用快排」，将这些组内元素全部排好序之后，然后运用败者树和置换-选择排序，进行多路归并，即可。

胜者树与败者树\
胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。

不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。

胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。 在k路归并排序中经常用到。

胜者树与败者树参考 <https://blog.csdn.net/whz\\_zb/article/details/7425152> <http://c.biancheng.net/view/3453.html>

<https://blog.csdn.net/FX677588/article/details/72471357> <https://www.jianshu.com/p/b8faa1affe17> <https://www.cnblogs.com/tonychen-tobeTopCoder/p/5797002.html> <https://blog.csdn.net/xiezhi123456/article/details/87632559> <https://blog.csdn.net/life\\_liver/article/details/8554133>