Order as humans understand it is different from physical order. We see order as an array of ascending numbers or a house of cards. The universe sees order more like a state of 'useful' energy, where it's possible to extract it, and seemingly became ordered by putting energy in. This is why I think the information theory definition of entropy is a bit misleading.

I like to see it as a radioactive atom, which starts as a useful structure with potential energy that has an inherent timer until this energy is lost due to the universe wanting to return to equilibrium. So it's statistically extremely unlikely to get the atom back to its original energetic state by nature, but not because because it's literally impossible, it's just impossible to do this without putting energy back in and that's not something that happens naturally.

A reversal of entropy is entirely possible, it's just called doing work. Of course, we don't have the knowledge necessary to reverse each individual atom in the melting process of an ice cube, but one day we might. It's theoretically possible with enough work. Of course, there will always be a loss of energy, but i'm pretty sure that's an entirely different thermodynamic law.