算法 Proc 2-way-exsort(file Read each page into memory, sort it, write it out While the number of runs at end of previous pass> 1 while there are runs to be merge from previous pass is choose next two runs(from previous pass) read each run into an input buffer; Merge the runs and write to the output buffer force output buffer to disk one page at a time wndproc
算法 Proc 2-way-exsort(file) Read each page into memory, sort it, write it out While the number of runs at end of previous pass>1 while there are runs to be merge from previous pass is choose next two runs(from previous pass) read each run into an input buffer; Merge the runs and write to the output buffer force output buffer to disk one page at a time endproc
计算量分析 ●若输入文件大小为2k,k为一个整数 Pass0,产生2个run,每个1页 Pass1,产生2k1个run,每个2页 ○Pass2,产生2k2个run,每个4页 ●总共需要og2N+1次pasN为文件的页数, 对每一页做一次读,一次写 ●总共的开销为:2NogN+1)
计算量分析 ⚫若输入文件大小为2 k ,k为一个整数 Pass 0，产生2 k个run，每个1页 Pass 1，产生2 k-1个run，每个2页 Pass 2，产生2 k-2个run，每个4页 ⚫总共需要log2N +1次pass,N为文件的页数， 对每一页做一次读，一次写 ⚫总共的开销为：2N*(log2N +1)
例子 3462948,75,63,12 3426497.856 2 2,3464,78,91,356 2 2,3446,78,9 2|3,56 122334456,67,8
例子 3,4 6,2 9,4 8,7 5,6 3,1 2 3,4 2,6 4,9 7,8 5,6 1,3 2 2,3 4,6 4,7 8,9 1,3 5,6 2 2,3 4,4 6,7 8,9 1,2 3,5 6 1,2 2,3 3,4 4,5 6, 6 7,8 9
外部 Merge排序 ●若内存中有B个 pages。如何利用2路 Merge 排序的思想,进行排序操作? O在pass0一次性读入B个页的数据进行排序 在pass1,2,一次性读入B个页的数据进行排序 利用B-1个 Buffer页作为输入,将最后一个 Buffer 页作为输出的缓冲区,进行B-1路的 Merge排序
外部Merge排序 ⚫若内存中有B个pages。如何利用2路Merge 排序的思想，进行排序操作？ 在pass 0一次性读入B个页的数据进行排序。 在pass 1,2,…一次性读入B个页的数据进行排序。 利用B-1个Buffer页作为输入，将最后一个Buffer 页作为输出的缓冲区，进行B-1路的Merge排序
算法 Proc export(file) Read B page into memory, sort them, write out a run While the number of runs at end of previous pass >1 while there are runs to be merged from previous pass choose next B-1 runs(from previous pass) read each run into an input buffer; page at at time Merge the runs and write to the output buffer force output buffer to disk one page at a time wndproc
算法 Proc exsort(file) Read B page into memory, sort them, write out a run While the number of runs at end of previous pass >1 while there are runs to be merged from previous pass choose next B-1 runs(from previous pass) read each run into an input buffer; page at at time Merge the runs and write to the output buffer force output buffer to disk one page at a time endproc