Pergunta de entrevista da empresa Google

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).

Sigiloso

18 de out. de 2010

Use mergesort.