There are no countable infinite sets on finite computers, and if you have a FINITE SET of input strings, the cardinality of the sets that represent the results of the presented regexs may very well differ and thus be sortable.

Let's do some arithmetic. Let's take a computer with 1 kB of memory - not unreasonable in 2010. For argument sakes, ignore any other memory, including disk space.

Limiting the problem space to all strings that can be stored on disk, you'd have 256¹⁰²⁴ finite strings to work with. 256¹⁰²⁴ is a finite number. Let's assume that each yoctosecond (10^-24s), you can analyse yotta-strings (10²⁴ strings). In other words, each second, you'd be able to determine of 10⁴⁸ ≅ 2¹⁶⁰ strings whether they match the given regexes. Then you still need about 10²⁴¹⁸ seconds to examine them all. The age of the universe is estimated to be about 13.75 billion years, which is about 4.4 * 10¹⁷ seconds.

So, yeah, there are no countable infinite sets on computers. But I don't think it's really practical to do a brute-force calculation of all the possible FINITE strings a computer can hold.