정렬 알고리즘 2 : 병합 정렬(합병 정렬, Merge sort)

두 번째로 알아볼 정렬 알고리즘은 바로 병합 정렬이다! 먼저 동작 방식을 간단하게 살펴보자 폰 노이만이 개발한 알고리즘으로 데이터 크기만 한 메모리가 더 필요하다는 점이 단점이다. 장점은 데이터의 상태에 영향을 받지 않는다는 점이 있다. 즉, 항상 O(n log(n))의 시간 복잡도를 갖는다. n-way 합병 정렬이라고 부르지만 나는 흔히 사용하는 2-way 합병 정렬을 알아보도록 하겠다. 리스트의 길이가 1이면 이미 정렬된 것으로 본다. (1개밖에 없으므로) 정렬되지 않은 리스트를 절반으로 잘라 두 개의 부분 리스트로 나눈다. 부분 리스트에 1, 2번 과정을 반복한다.(재귀 이용) 잘게 쪼개진 부분리스트 들을 임시 리스트에 합병해가면서 정렬한다. 임시 배열에 저장된 결과를 원래 배열에 복사한다. 과정을..

원문링크 : 정렬 알고리즘 2 : 병합 정렬(합병 정렬, Merge sort)