我正在阅读“Programming Pearls”，我对其中一个解决方案解释感到非常困惑。
问题是：“一个文件最多包含 n 个正整数，每个小于 n，其中 n = 10^7。每个正整数最多可以出现十次。你会如何对文件进行排序？”
书中给出的解决方案： “如果每个整数最多出现十次，那么我们可以在一个四位半字节中计算它的出现次数。使用问题 5（如下）的解决方案，我们可以一次性对整个文件进行排序10,000,000/2 字节，或在 k 次传递中 10,000,000/2k 字节"
问题 5 的解决方案是：双通道算法首先使用 5,000,000/8 = 625,000 个字的存储空间对整数 0 到 4,999,999 进行排序，然后在第二遍中对 5,000,000 到 9,999,999 进行排序。k-pass 算法在时间 kn 和空间 n/k 上最多排序 n 个小于 n 的非重复正整数。）
我不知道作者是如何到达 10,000,000/2k 空间进行排序的。我的意思是，基于问题 5 的解决方案，首先我们需要 625K 字节的空间来进行第一遍排序，并且每个整数需要额外的 1/2 字节来存储计数，对吗？
有人可以帮我理解这一点吗？
非常感谢。