Mesclar listas ordenadas
Mesclar duas listas ordenadas sem usar sort() é uma operação comum em algoritmos como o merge sort, na combinação de logs ordenados por data ou na junção de dados de fontes diferentes. Saber fazer isso manualmente evita o custo de ordenar novamente (O(n log n)) e garante eficiência O(n).
O PROBLEMA
Mescle duas listas ordenadas mantendo ordem sem sort().
EXEMPLO
[1,2,3,4,5,6,7,8]
SOBRE O CONCEITO
Para mesclar, usam-se dois índices que percorrem as listas, comparando os elementos atuais e anexando o menor. O erro comum é esquecer de adicionar os elementos restantes de uma lista após a outra ter sido completamente percorrida. Isso ocorre porque o loop principal termina quando um índice chega ao fim, deixando elementos sem tratamento. A solução é, após o loop principal, incluir dois loops while extras para esvaziar a lista que ainda contiver elementos. Como for é proibido, usa-se while com incremento manual dos índices.
RESOLUÇÃO