Merge de listas
Mesclar duas listas ordenadas sem usar sort() é uma operação comum em sistemas que precisam combinar dados de fontes ordenadas, como logs de servidores ou resultados de consultas paginadas. Saber fazer isso manualmente garante performance linear O(n) e controle fino sobre o processo, além de ser uma habilidade cobrada em entrevistas técnicas.
O PROBLEMA
Mescle dois ArrayLists ordenados mantendo ordem sem sort().
EXEMPLO
[1,2,3,4,5,6,7,8]
SOBRE O CONCEITO
O algoritmo de merge percorre as duas listas simultaneamente com índices, comparando elementos e adicionando o menor à lista resultado. O erro mais comum é esquecer de adicionar os elementos restantes de uma lista depois que a outra termina, pulando itens e corrompendo o resultado. Para evitar isso, após o while principal, use dois while adicionais para esvaziar cada lista restante. Como Collections.sort é proibido, você mesmo deve garantir a ordenação incremental durante a mesclagem.
RESOLUÇÃO