Python 병합 정렬
입력을 재귀적으로 나눈 뒤 정렬된 부분 리스트를 병합합니다.
병합 정렬이란?
입력을 재귀적으로 나눈 뒤 정렬된 부분 리스트를 병합합니다.
분할 정복 방식으로 데이터를 정렬합니다.
언제 사용하나요?
- 알고리즘과 자료 구조를 이해합니다.
- 각 단계와 경계 조건을 확인합니다.
- 실행 시간과 메모리 사용량을 비교합니다.
Python 병합 정렬 시각화
O(n log n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
main.py
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))예상 출력
[3, 9, 10, 27, 38, 43, 82]작동 원리
시간 O(n log n)을 보장하며 O(n)의 추가 메모리를 사용합니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
입력값과 경계 조건을 바꾸고 더 큰 데이터에서도 동작을 확인하세요.
- 빈 입력, 한 요소, 중복값을 시험하세요.
- 각 단계의 상태를 출력하세요.
- 다른 풀이와 성능을 비교하세요.