I am a bit shady on the details and could quite easily be wrong...
I believe that 'pure' software patents technically are 'illegal' in the USA also. Just like in the EU they are not patentable. However the combination of 'software' and 'hardware' creates a patentable invention.
So to get around this limitation every single 'software patent' references many times to the fact that it involves running on actual hardware. Since software is nothing without hardware then this means that pretty much any software algorithm is patentable as soon as you try to actually use it.
The key thing is that you can't try to make sense of it. Patents and what is patentable and is not patentable is completely arbitrary. People try to draw lines about physical inventions or algorithms and such things, but that isn't really relevant. It's purely 'decide by committee' law that is not based on any naturally occurring concept or natural practice by human beings... therefore common sense doesn't apply.