slamb
Re:Sorting a million 32-bit integers in 2MB of RAM using Python
on Sunday January 04, 2009 @12:31AM (#419032)
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.