Marge Sort (합병 정렬)

합병 정렬은 비교 기반 정렬의 알고리즘으로 분할 정복 알고리즘^[각주:1]의 하나이다.

합병 정렬은 아래와 같이 동작한다.

1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

아래 그림을 보면 이해가 빠를 듯 하다.

구현된 Class는 아래와 같다.

class MergeSort { private void merge(int[] arr, int startPoint, int midPoint, int endPoint) { int n1 = midPoint - startPoint + 1; int n2 = endPoint - midPoint; ​ int[] L = new int[n1]; int[] R = new int[n2]; ​ for (int i = 0; i < n1; ++i) { L[i] = arr[startPoint + i]; } ​ for (int j = 0; j < n2; ++j) { R[j] = arr[midPoint + 1 + j]; } ​ int x = 0; int y = 0; int z = startPoint; ​ while (x < n1 && y < n2) { if (L[x] <= R[y]) { arr[z] = L[x]; x++; } else { arr[z] = R[y]; y++; } ​ z++; } ​ while (x < n1) { arr[z] = L[x]; x++; z++; } ​ while (y < n2) { arr[z] = R[y]; y++; z++; } } ​ public void divide(int[] arr, int startPoint, int endPoint) { if (startPoint < endPoint) { int midPoint = (startPoint + endPoint) / 2; ​ divide(arr, startPoint, midPoint); divide(arr, midPoint+1, endPoint); ​ merge(arr, startPoint, midPoint, endPoint); } }   }

시간복잡도는 O(nlogn)이며, 안정적 정렬에 속한다.

참조 1 : https://ko.wikipedia.org/wiki/합병_정렬

참조 2 : http://geeksquiz.com/merge-sort/

1. 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. [본문으로]