알고리즘, 자료구조
[정렬] 합병정렬
합병정렬(merge sort)부터는 기본 정렬(버블, 선택, 삽입)보다 약간 복잡해진다. 하지만 성능은 훨씬 좋아진다. 정렬 알고리즘에서 빼놓을 수 없는 합병정렬에 대해 한 번 공부해보자. 폰 노이만 합병정렬은 폰노이만이 1945년에 개발한 정렬 알고리즘이다. 기초적인 정렬 알고리즘들(선택, 버블, 삽입)은 아무리 효율성을 고려한다고 해도 결국 배열을 싹 훑어내면서 정렬을 해야하는, 태생적인 O(N^2)의 시간복잡도를 가졌었다. 하지만 폰 노이만의 합병정렬은 알고리즘에 분할과 정복을 도입하여 정렬의 시간 복잡도를 크게 낮추었다. 발상 자체가 굉장히 천재적이다. 합병정렬의 분할과 정복(합병) 최대한 추상적으로 설명해보자면... 분할 먼저 정렬할 배열을 반으로 분할한다. 받은 배열을 또 절반으로 나눈다. 절..
