정렬된 두 배열 합치기

왜 이 문제를 푸나요?

두 정렬 결과를 다시 정렬하지 않고 선형 시간에 합치는 과정은 병합 정렬의 핵심입니다. 두 포인터가 각각 한 방향으로만 움직이는 패턴을 익힙니다.

오름차순으로 정렬된 두 리스트를 하나의 오름차순 리스트로 합치세요. 모든 원소와 중복을 유지하며 sorted()나 sort()는 사용하지 않습니다.

merge_sorted(left, right)

시간 O(n+m), 공간 O(n+m)

실행하면 아래 순서대로 채점합니다. print() 출력도 이 순서대로 쌓입니다.

#	이름	`left`	`right`	기대값
1	서로 교차	`[1, 4, 8]`	`[2, 3, 9]`	`[1, 2, 3, 4, 8, 9]`
2	중복 유지	`[1, 2, 2]`	`[2, 5]`	`[1, 2, 2, 2, 5]`
3	한쪽이 비어 있음	`[]`	`[3, 7]`	`[3, 7]`
4	양쪽 모두 비어 있음	`[]`	`[]`	`[]`
5	음수 교차	`[-7, -1, 4]`	`[-5, 0, 6]`	`[-7, -5, -1, 0, 4, 6]`

Python 표준 라이브러리는 사용할 수 있습니다. 함수 이름과 매개변수는 제시된 형태를 유지하세요.