Brachylog (v2), 5 bytes, language postdates challenge

≤₁|ṣ↰

Try it online!

Function submission. (The TIO link uses a command-line argument that automatically wraps a function into a full program.)

Explanation

≤₁|ṣ↰
≤₁      Assert that {the input} is (nonstrictly) sorted in ascending order
  |     Output it
  |     Exception handler: if an assertion fails:
   ṣ      Randomly shuffle {the input}
    ↰     and run this function recursively on it, {outputting its output}

Prolog (the language that Brachylog compiles into) is tail-recursive, so this function ends up being compiled into a tight loop.