Nearly all websites assert that Excel "stores" 15 significant decimal digits of precision for numeric values. That does not make them right. In fact, they are wrong !
Apparently, that is also the case with regard to your question about the order of values in the bins array. (Suprise !)
For a more visible demonstration, enter 1, 3, 3, 5, 5, 5, 7, 7, 7, 7 into A1:A10.
Select B1:B5 and array-enter =FREQUENCY(A1:A10,{7,5,3,1})). Note that the correct counts are returned, namely 4,3,2,1, but in the order of the bins array values.
Select C1:C5 and array-enter =FREQUENCY(A1:A10,{1,3,5,7}). Note that, again, the correct counts are returned in the order of the bins array values.
Finally, normally-enter the formula =MATCH(A1,{7,5,3,1}) into D1. Copy D1 and paste into D2:D10. Note that either #N/A or the wrong index is returned except for 5, by coincidence.
That demonstrates that if FREQUENCY depended on ascending order and performed a binary search of the bins array, like MATCH, FREQUENCY would have returned errors or erroneous results.
So I agree with "XOR XL": these exercises, as well as your own, seem to demonstrate that FREQUENCY is not sensitive to the order of values in bins array, notwithstanding "conventional wisdom".
Nevertheless, the only way to prove the assertion is to find MSFT documentation that supports it. Otherwise, there might exist a counter-example that disproves the conclusion. (And unfortunately, MSFT is not dispositive, because it is sometimes incorrect.)
For that reason, I would not depend on undocumented behavior.