Resulting in O(n + k log k + 2k). In this particular case one might even argue that n > k log k + 2k, therefore O(2n) = O(n) However, it's late here and I don't like to argue.
You only need enough memory to keep the new addresses in memory and enough disk space to keep both the new and old version on disk at the same time.
You are correct. I had not considered updating the list not from scratch. Accessing a single line from a file can degrade performance, and it should be considered if paying for more RAM would be cost effective considering the additional time required to update the list.