At lazy glance, it looks kind of like Quadsort has re-derived a variation of the 4-element sorting network.
In section 2 in that Wikipedia article, it links to many constructions that do exactly that.
A couple are O(n log(n)), but complicated and impractical. The algorithms people use are O(n log^2(n)) ones.
FWIW, sorting networks are data-independent. I.e. for any input, you always compare-and-swap the same elements.
"For one to eleven inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉. The first ten optimal networks have been known since 1969, with the first eight again being known as optimal since the work of Floyd and Knuth, but optimality of the cases n = 9 and n = 10 took until 2014 to be resolved. An optimal network for size 11 was found in December of 2019 by Jannis Harder..."
Clearly I also should've said < ~12.
The search space is infinite, so exhaustively exploring it is impossible.
Procedures that enumerate Turing machines are generally very easy, or nigh impossible
O(n log n) is only the frontier for comparison based sorts that know nothing about the distribution of inputs.
If your sorting algorithm is allowed to do anything else on your data, like hashing or looking at bits or arithmetic, different lower bounds might apply.