algorithm_merge
algorithm_merge (병합)
std::merge는 두 정렬된 소스 범위의 모든 요소를 포함하는 정렬된 수열을 만들어 목적지 범위에 복사해요. 병합 정렬(merge sort)의 핵심 연산이에요.
출처: cppreference
본문
std::merge는 두 정렬된 소스 범위 [first1, last1)과 [first2, last2)의 모든 요소를 포함하는 가상의 정렬된 수열을 구성하고, 그 수열의 모든 요소를 d_first에서 시작하는 목적지 범위로 복사해요. <algorithm> 헤더에 정의되어 있어요.
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first );
template< class InputIt1, class InputIt2,
class OutputIt, class Compare >
OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first, Compare comp );
- 1번 오버로드 — 요소를
operator<(즉std::less{})로 비교해요. - 2번 오버로드 — 요소를 비교 함수
comp로 비교해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
merge는 안정적이라, 동등한 요소일 때 첫 번째 범위의 요소가 두 번째 범위의 요소보다 먼저 나와요.
반환값 (Return value)
복사된 마지막 요소 다음의 반복자예요.
복잡도 (Complexity)
최대 N₁ + N₂ - 1번의 비교가 필요해요 (여기서 N₁ = std::distance(first1, last1), N₂ = std::distance(first2, last2)).
예제 (Example)
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> v1{1, 3, 5};
std::vector<int> v2{2, 4, 6};
std::vector<int> dst;
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(dst));
for (int x : dst) std::cout << x << ' ';
std::cout << '\n';
}
출력:
1 2 3 4 5 6