7226 : 합병 정렬 구현
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
합병 정렬(Merge Sort)은 분할 정복 전략을 사용하는 정렬 알고리즘입니다.
배열을 절반으로 나누고 각각을 재귀적으로 정렬한 후, 두 정렬된 배열을 합병하여 전체를 정렬합니다.
시간 복잡도는 $O(N \log N)$으로 안정적이며 대용량 데이터에 적합합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
배열을 절반으로 나누고 각각을 재귀적으로 정렬한 후, 두 정렬된 배열을 합병하여 전체를 정렬합니다.
시간 복잡도는 $O(N \log N)$으로 안정적이며 대용량 데이터에 적합합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.
출력 설명
합병 정렬을 이용하여 오름차순으로 정렬된 배열을 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6
5 3 8 4 2 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2 3 4 5 7 8도움
재귀 함수
merge_sort(arr, l, r)를 정의하고, 중간점 mid = (l+r)//2를 기준으로 좌우 배열을 각각 재귀 호출한 후 두 포인터로 합병합니다.