Qual é a complexidade algorítmica da operação de união de vários arrays com ordenação do resultado obtido?

A união de vários arrays e a subsequente ordenação do resultado geralmente têm a seguinte complexidade algorítmica:

1. Suponha que temos k arrays, cujo tamanho total é n.
2. A união de arrays é uma operação de cópia de elementos, que é realizada em O(n).
3. A ordenação do array combinado leva O(n log n) tempo, se for utilizado um algoritmo de ordenação eficiente (por exemplo, ordenação rápida ou por fusão).

No total, a complexidade geral é — O(n log n).

Se os arrays originais já estiverem ordenados, pode-se usar um algoritmo de fusão de k arrays ordenados, o que permitirá obter o resultado em O(n log k), sendo mais eficiente quando há muitos arrays.