External Mergesort Cost Analysis
Critical operations: read an Item, write an Item
- each pass = N reads + N writes
- #iterations = ceil( log2N )
- Cost = 2N ceil( log2N ) = O(NlogN)
Works on any file that can be stored three times in the file system.
This approach is used by the Unix/Linux sort command.
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}