algorithm_inplace_merge
algorithm_inplace_merge (제자리 병합)
std::inplace_merge는 각각 정렬된 두 연속 부분 범위 [first, middle)과 [middle, last)를 병합해서 전체 범위 [first, last)를 정렬된 상태로 만들어요. 추가 메모리를 거의 쓰지 않는 제자리 연산이에요.
출처: cppreference
본문
std::inplace_merge는 두 개의 연속된 정렬 부분 범위 [first, middle)과 [middle, last)를 병합해서 대상 범위 [first, last)를 정렬되게 만들어요. <algorithm> 헤더에 정의되어 있어요.
template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );
template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
Compare comp );
정렬된 대상 범위의 동등한 요소 그룹 각각에 대해, 그룹의 요소들이 다음 순서를 가져요:
- 두 요소가 같은 부분 범위에서 왔으면, 대상 범위에서의 순서는 부분 범위에서의 원래 순서를 따르고,
- 그렇지 않으면
middle에 더 가까운 부분 범위의 요소가 먼저 나와요.
이렇게 inplace_merge는 안정적(stable)이에요. 병렬 실행 정책을 받는 오버로드도 있어요.
복잡도 (Complexity)
적절한 추가 메모리가 있다면 std::distance(first, last) - 1번의 비교(또는 comp 적용)와 std::distance(first, last)번의 이동이 필요해요. 추가 메모리가 없으면 𝓞(N·log N)의 비교와 이동이 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{2, 4, 6, 1, 3, 5};
auto middle = std::next(v.begin(), 3);
std::inplace_merge(v.begin(), middle, v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
출력:
1 2 3 4 5 6