Kronrod's in-place merge

Kronrod's merge was the first published algorithm to do that. It goes roughly like this:

Split both parts of the array into blocks of size k=sqrt(n). Sort the blocks using their first elements as the basis for comparison. This can be done in sqrt(n)^2=O(n) by selection sort. Now merge the first block with the second, then second with the third, etc., using the last 2 blocks as temporary space for the output of the merge. This will scramble the contents of the last two blocks but in the last p

文件:	643.full.pdf
大小:	984KB
下载:	下载

hase they (together with the preceding block) can be sorted by selection sort in sqrt(n)^2=O(n) time.