7278 : 재귀 합병정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
합병 정렬을 재귀 함수로 구현하십시오.
재귀 원리: 배열을 절반으로 분할하여 각각 재귀 정렬 후 합병합니다.
분할 정복의 대표적 예시이며 시간 복잡도는 $O(N \log N)$입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
재귀 원리: 배열을 절반으로 분할하여 각각 재귀 정렬 후 합병합니다.
분할 정복의 대표적 예시이며 시간 복잡도는 $O(N \log N)$입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 크기 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
둘째 줄에 정수 배열이 주어집니다.
둘째 줄에 정수 배열이 주어집니다.
출력 설명
재귀 합병 정렬로 정렬한 오름차순 배열을 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6
5 3 8 4 2 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2 3 4 5 7 8도움
def merge_sort(arr): if len(arr)<=1: return arr; mid=len(arr)//2; left=merge_sort(arr[:mid]); right=merge_sort(arr[mid:]); return merge(left,right)