정렬된 두 시퀀스 병합하기

두 개의 정렬된 리스트가 주어졌을 때 하나의 정렬된 리스트로 합치십시오. 이 병합은 병합 정렬의 핵심이며 여러 곳에서 활용됩니다. 🔗

각 리스트에 포인터를 하나씩 두고, 둘 다 인덱스 0에서 시작하십시오. 두 포인터를 뒤로 가지 않고 함께 앞으로 이동합니다.

각 단계에서 두 리스트의 맨 앞 원소를 비교하십시오. 정렬된 순서에서 다음에 와야 하는 값이므로 더 작은 값을 결과에 추가하십시오.

값을 선택한 뒤에는 그 값이 있던 포인터만 이동하십시오. 다른 리스트에는 여전히 가장 작은 원소가 기다리고 있습니다.

두 리스트 모두에 원소가 남아 있는 동안 계속 병합하십시오. 어느 한쪽이 먼저 소진되면 더 이상 비교할 수 없습니다.

한 리스트가 비면 다른 리스트는 이미 정렬되어 있으므로, 남은 뒤쪽 부분을 결과에 그대로 append하십시오.

남은 뒤쪽 부분은 이미 순서가 맞으므로 더 비교할 필요가 없습니다. 두 extend 호출 중 하나는 아무것도 추가하지 않습니다.

모든 원소를 한 번씩만 확인하므로 크기가 각각 n과 m인 두 리스트를 병합하는 데 O(n + m) 시간이 걸립니다. 이것이 가능한 가장 빠른 방법입니다.

값이 같을 때 <=를 사용하면 같은 값끼리 원래 순서를 유지합니다. 추가 데이터를 함께 다룰 때 이러한 안정성이 중요합니다.

남는 공간이 없는 버퍼에 병합하려면 뒤쪽에서부터 이동하며 가장 큰 원소를 마지막에 배치하십시오. 같은 아이디어를 반대로 적용하는 것입니다.

나누고, 각 절반을 정렬한 다음, 병합하십시오. 이 재귀가 바로 병합 정렬입니다. 방금 배운 두 포인터 병합이 그 핵심 동작입니다.

각 리스트에 포인터 하나씩 두고 두 정렬된 리스트를 병합하고 있습니다.

두 정렬된 리스트를 각각 포인터 하나로 훑으며 항상 더 작은 맨 앞 원소를 선택한 다음, 남은 뒤쪽 부분을 처리하십시오. O(n + m)에 동작하며 병합 정렬의 기반이 됩니다. 🚀