"Blessed rage for order, pale Ramon..."

So, the big cost center is nDigitYs. All it does is concatenate our three flavors of Y (the ones with no 2s, the ones with one 2, and the ones with two 2s) and sort them. Of the d-digit Ys, there are at most two with two 2s, and there are d `div` 2 with one 2. By far the majority are those with no 2s; for d == 49, of the 4,122 Ys, 4,122 - 2 - 24 = 4,096 have no 2s.

We know that the two-2 Ys are greater than all the others, so we could go with

nDigitYs n = sort (noTwos n ++ oneTwos n) ++ twoTwos n

...for what little good that does.

If you take a look at the result of oneTwos, you'll find that they're always in ascending order; we grind them out so that the optional 1 is first not there, and then in ascending order in the most signfiicant half, which suffices to order them. noTwos, on the other hand, isn't, for d > 7.  If there's some way to generate them in ascending order, we could go with

nDigitYs n = merge (noTwos n) (oneTwos n) ++ twoTwos n

(be sure to import Data.List.Utils) and O(n) beats O(n log n) any day. Unfortunately, I don't know of a good way to do that.