병합정렬(merge sort)은 대표적인 정렬 알고리즘 중 하나로 다음과 같이 동작합니다.
1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
(출처 : 위키피디아)
다음 코드의 빈칸을 채워 병합정렬을 완성해 봅시다.
#병합 정렬 def 병합정렬(입력리스트): 입력리스트길이 = len(입력리스트) if 입력리스트길이 <= 1: return 입력리스트 중간값 = 입력리스트길이 // 2 그룹_하나 = 병합정렬(입력리스트[:중간값]) 그룹_둘 = 병합정렬(입력리스트[중간값:]) 결과값 = [] while (#빈칸을 채워주세요) and (#빈칸을 채워주세요) : if (#빈칸을 채워주세요): 결과값.append(그룹_하나.pop(0)) else: 결과값.append(그룹_둘.pop(0)) while 그룹_하나: 결과값.append(그룹_하나.pop(0)) while 그룹_둘: 결과값.append(그룹_둘.pop(0)) return 결과값 주어진리스트 = [180, 145, 165, 45, 170, 175, 173, 171] #빈칸을 채워주세요 print(병합정렬(주어진리스트))