1. 外部排序演算法基本思想是什麼
外部排序的基本思路
假設有一個72KB的文件，其中存儲了18K個整數，磁碟中物理塊的大小為4KB，將文件分成18組，每組剛好4KB。
首先通過18次內部排序，把18組數據排好序，得到初始的18個歸並段R1~R18，每個歸並段有1024個整數。
然後對這18個歸並段使用4路平衡歸並排序：
第1次歸並：產生5個歸並段
R11 R12 R13 R14 R15
其中
R11是由{R1,R2,R3,R4}中的數據合並而來
R12是由{R5,R6,R7,R8}中的數據合並而來
R13是由{R9,R10,R11,R12}中的數據合並而來
R14是由{R13,R14,R15,R16}中的數據合並而來
R15是由{R17,R18}中的數據合並而來
把這5個歸並段的數據寫入5個文件：
foo_1.dat foo_2.dat foo_3.dat foo_4.dat foo_5.dat
第2次歸並：從第1次歸並產生的5個文件中讀取數據，合並，產生2個歸並段
R21 R22
其中R21是由{R11,R12,R13,R14}中的數據合並而來
其中R22是由{R15}中的數據合並而來
把這2個歸並段寫入2個文件
bar_1.dat bar_2.dat
第3次歸並：從第2次歸並產生的2個文件中讀取數據，合並，產生1個歸並段
R31
R31是由{R21,R22}中的數據合並而來
把這個文件寫入1個文件
foo_1.dat
此即為最終排序好的文件。
二 使用敗者樹加快合並排序
外部排序最耗時間的操作時磁碟讀寫，對於有m個初始歸並段，k路平衡的歸並排序，磁碟讀寫次數為
|logkm|，可見增大k的值可以減少磁碟讀寫的次數，但增大k的值也會帶來負面效應，即進行k路合並
的時候會增加演算法復雜度，來看一個例子。
把n個整數分成k組，每組整數都已排序好，現在要把k組數據合並成1組排好序的整數，求演算法復雜度