https://www.acmicpc.net/problem/11728

정렬되어있는 두 배열을 합쳐서 정렬되어있는 상태를 유지하는데에는 O(N+M)이 필요합니다. 이는 Merge sort를 할 때에도 필요한 알고리즘입니다.

예를 들어

1 2 4 7 8 10

3 6 11 16

- - - - - - - - - - -

을 합친다고 하면, 먼저 1과 3을 비교합니다. 이 때 작은 것을 취하고, 원래의 배열에서 지웁니다.(실제로 지우는 연산을 취하지는 않지만 관념적으로 지웠다고 합시다.)

x 2 4 7 8 10

3 6 11 16

1 - - - - - - - - - -

이제 2와 3을 비교합니다. 마찬가지로 2를 취하고, 원래의 배열에서 지웁니다.

x x 4 7 8 10

3 6 11 16

1 2 - - - - - - - - -

이제 4와 3을 비교합니다. 3을 취하고 원래의 배열에서 지웁니다.

x x 4 7 8 10

x 6 11 16

1 2 3 - - - - - - - -

이를 반복하면 한 번의 비교에 원소 N+M개 중 어느 하나는 반드시 제자리를 찾아가기 때문에 O(N+M)임을 알 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/11728.cpp