time-complexity - 对包含大量数据的文件进行排序

Question

考虑一个包含N每行一个单词的单词的文件。该文件太大，因此无法一次在内存中读取整个文件。
我的回答：将文件分成k chunks.So 每个块的大小 一次将一个块x = N/k
读入内存并对其进行排序并写回文件。对所有 k 个块进行排序。
现在做一个k way merge.
分析总时间复杂度。我该怎么做？
对每个块进行排序的时间= xlogx（假设我使用快速排序）
合并k个块的时间= klogk（是吗？？）
所以总时间复杂度=??
分析时间复杂度的一周

Answer 1

每个块的大小为 N/k，块的数量为 k。

因此，总时间复杂度为

读取 N/k 个块 + 对这些块中的每一个进行排序，即 O( N/k klogk) + 合并这些 k 个块中的每个 [部分] O( Nk ) + 文件写入。

所以，这将是 IO 时间 + O(Nlogk)

我也在学习这些东西......所以如果我在这里错了，如果有人能分析和纠正我，那就太好了..

-帕万。