pri*_*sia 11 sorting algorithm data-structures
这是一个Google采访问题:给定2台机器,每台机器有64 GB RAM,包含所有整数(8字节),对整个128 GB数据进行排序.您可以假设少量额外的RAM.扩展它以对存储在1000台机器中的数据进行排序.
我提出了外部排序.我们将整个数据划分为块并对它们使用合并排序.这是第一种块并将它们放回去并再次将它们合并并合并它们.有没有更好的办法？复杂性会是什么？
每个 64 GB 都可以单独使用快速排序进行排序，然后使用外部存储器将指针保留在两个 64 GB 数组的头部，让我们考虑一下我们希望 RAM1 和 RAM2 按此顺序拥有整个数据，如果如果它小于 RAM2 中的指针值，否则将值与 RAM2 交换，直到指针到达 RAM1 的末尾。
采用同样的概念对所有 N 个 RAM 进行排序。取它们对并使用上述方法进行排序。剩下 N/2 个已排序的 RAM。递归地使用上面相同的概念。