How would you sort a file which is too large to fit in memory.
Respostas da entrevista
Sigiloso
10 de nov. de 2010
the correct answer is an external sorting algorithm which is more complex than just mergesort. see external sort on wikipedia.
3
Sigiloso
25 de fev. de 2011
Split the file into k chunks of size n. Sort them in time k(n log n). Then you can merge them in log k layers in a binary tree sort of structure, taking time kn for each layer.
Total time will be k(n log n) + kn(log k) = kn (log n + log k) = kn(log kn).