I believe your ideal storage requirement, but what's the time complexity of your algorithm, and could you describe it in more detail than "clever"?
I'm pretty sure random reads and writes on any compressed form will be worse than O(1), and I'm pretty sure your sort will do O(n log n) of those, so I believe your algorithm is asymptotically (and in practice for n = 1 million) slower than chmike's two-pass algorithm.
I was thinking along eru's lines. The specifics I came up with:
1) Compress sorted lists by encoding the differences between successive numbers using a code that's shorter for smaller numbers.
2) Use in-memory merge sort. That way you don't need random access to the lists, and it's overall O(n log n).
3) In order to merge large lists when memory is already almost full, divide the lists into blocks, allocate blocks for the merged list while you're deallocating blocks from the two source lists.
4) To do this in Python, use the "array" module.
I'm pretty sure random reads and writes on any compressed form will be worse than O(1), and I'm pretty sure your sort will do O(n log n) of those, so I believe your algorithm is asymptotically (and in practice for n = 1 million) slower than chmike's two-pass algorithm.