inplace_merge
inplace_merge (제자리 병합 정렬)
같은 범위 안에서 이미 각각 정렬된 두 연속 구간 [first, middle)과 [middle, last)을 하나의 정렬된 범위로 제자리에서 병합하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
inplace_merge은 두 개의 정렬된 연속 구간을 제자리에서 하나의 정렬된 구간으로 병합해요.
template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ); // (1)
비교기 comp를 받는 버전도 있어요.
template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
Compare comp ); // (2)
-
operator<로, 2)comp로 비교해요.
- C++17부터 실행 정책 오버로드가 추가됐어요.
복잡도는 추가 메모리(middle - first 크기의 임시 버퍼)가 있으면 last - first - 1번의 비교, 임시 버퍼가 없으면 N·log₂N번의 비교가 필요할 수 있어요. 어떤 경우든 last - first - 1번의 이동이 필요해요.
std::vector<int> v{1, 3, 5, 2, 4, 6};
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
// v == {1,2,3,4,5,6}
병합 정렬(merge sort)의 합병 단계를 제자리에서 수행하는 함수예요. 임시 버퍼를 안 쓸 때 메모리는 아끼지만 시간은 더 걸릴 수 있다는 trade-off가 있어요.