[Alex] 데이터 장인의 블로그

병합 정렬 알고리즘도 대표적인 '분할 정복' 방법을 채택한 알고리즘. 퀵정렬과 동일하게 O(NlogN)의 시간복잡도를 가진다. 주어진 원소를 원소 하나만 남을 때까지 쪼갠 후에 다시 크기 순으로 재배열하면서 원래 크기의 배열로 합친다. 아래 리스트가 있다고 가정해보자. [6, 5, 3, 1, 8, 7, 2, 4] 각 원소마다 하나의 리스트가 생기도록 쪼갠 후에 역으로 두개씩 합치는 과정을 시작한다. [6] [5] [3] [1] [8] [7] [2] [4] 합칠때는 작은 숫자가 앞에 오도록 위치, 이후 각각 2개의 배열을 하나의 배열로 합치는 작업을 수행한다. [5, 6] [1, 3] [7, 8] [2, 4] 두개의 인자중 작은 인자부터 하나씩 비교하기 시작하면 작은 값부터 차례대로 배열을 정리할 수 있다..