Time complexity is probably dominated by the
Array.sort
call, that, according to this page
Time Comparison of Arrays.sort(Object[]) and Arrays.sort(int[]) | Baeldung[
^] is
O(n log(n))
.
There are still few little improvements you can make to your code in order to make it faster (e.g. first separate odd and even numbers then sort the corresponding arrays, avoid doing additional conditional tests: once you pick the first item then you have to pick items alternatively from the two arrays, without testing each time, ...).