Mescle Duas Sequências Ordenadas
Percorra as duas listas com um ponteiro em cada uma.
Mescle Duas Sequências Ordenadas é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
A Etapa de Intercalação
Dadas duas listas ordenadas, combine-as em uma única lista ordenada. Essa intercalação é o coração da ordenação por intercalação e aparece em muitos lugares. 🔗
Duas Entradas, Um Ponteiro para Cada Uma
Dê a cada lista seu próprio ponteiro, ambos começando no índice 0. Você avançará pelos dois simultaneamente, nunca para trás.
i = 0
j = 0Escolha Sempre o Menor
A cada etapa, compare os dois primeiros elementos. Use append para adicionar o menor ao resultado, pois ele deve vir em seguida na ordem crescente.
Avance o Vencedor
Depois de escolher um valor, avance apenas o ponteiro de onde ele veio. A outra lista ainda tem seu menor elemento aguardando.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1O Laço Principal
Continue intercalando enquanto as duas listas ainda tiverem elementos. Quando uma delas acabar, a comparação deixará de fazer sentido.
while i < len(a) and j < len(b):
# compare and append
passEsvazie o que Restou
Quando uma lista ficar vazia, a outra já estará ordenada, então basta usar append para adicionar diretamente o trecho restante ao resultado.
out.extend(a[i:])
out.extend(b[j:])Por Que os Trechos Restantes Não Custam Nada
O trecho restante já está ordenado, portanto não são necessárias mais comparações. Uma das duas chamadas a extend simplesmente não adiciona nada.
Tempo Total Linear
Cada elemento é examinado uma vez, portanto intercalar duas listas de tamanhos n e m custa O(n + m) de tempo. Essa é a maior velocidade possível.
Mantenha a Estabilidade
Usar <= quando os valores forem iguais mantém os elementos iguais na ordem original. Essa estabilidade é importante quando você transporta dados adicionais.
Intercale Também na Ordem Inversa
Para intercalar em um espaço de armazenamento sem espaço livre, percorra a partir do final, colocando o maior elemento por último. É a mesma ideia, invertida.
Da Intercalação à Ordenação
Divida, ordene as metades e depois intercale: essa recursão é a ordenação por intercalação. A intercalação com dois ponteiros que você acabou de aprender é seu mecanismo central.
Verificação Rápida
Você está intercalando duas listas ordenadas com um ponteiro em cada uma.
Recapitulação
Percorra duas listas ordenadas com um ponteiro em cada uma, escolhendo sempre o primeiro elemento menor e depois esvaziando o trecho restante. O processo executa em O(n + m) e é a base da ordenação por intercalação. 🚀
Perguntas Frequentes
A aula “Mescle Duas Sequências Ordenadas” é grátis?
Sim — o texto completo de “Mescle Duas Sequências Ordenadas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Mescle Duas Sequências Ordenadas”?
Percorra as duas listas com um ponteiro em cada uma. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Mescle Duas Sequências Ordenadas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Dois Ponteiros em um Array Ordenado
- Encontre um Par com uma Soma Determinada
- Remova Duplicatas no Próprio Array
- Mescle Duas Sequências Ordenadas