Isn't median-of-three approach is still O(n^2) worst-case. You'd need Blum–Floyd–Pratt–Rivest–Tarjan Median of Medians to get O(n), although it will probably be very slow. Or randomize quickselect in order to get good average case probability.

It looks to me like you are sorting a bunch of numbers in a array then return them as a link list. It doesn't sounds like merge several different link lists together.