합병 정렬

[알고리즘][파이썬/Python] 병합 정렬 (Merge Sort)

정의 입력 자료를 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 다음에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법 중 하나로, 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식의 정렬 알고리즘 동작 방식 (2-way 병합, 오름차순 정렬 기준) 0. 일반적으로 정렬한 상태의 자료를 담기 위해 입력 자료의 크기만큼의 새로운 배열(리스트)을 선언해줌. 그러나 해당 포스팅에 기재한 소스코드는 정렬한 원소를 새로운 리스트에 담지 않고 입력값인 기존의 리스트를 재사용했음. 동작 방식에 대한 설명은 새로운 리스트를 선언했다고 가정한 채 진행. 1. 입력 자료를 두 개의 부분집합으로..