반응형

Merge sort(병합 정렬)는 원소들 간의 비교를 통해 정렬하는 비교 기반 정렬 알고리즘이다.

원소들 중 같은 값이 있는 경우 정렬 후에도 순서가 유지된다.

정렬의 과정은 분할 -> 정복 -> 합병(결합) 의 순서로 이루어진다.

합병 정렬은 다음과 같이 작동한다.

  1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
  5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

시간 복잡도는 N 개의 데이터를 정렬할 때를 기준으로 O(N * logN)이다.

Merge sort의 정렬과정을 예를 들면 아래와 같다.

Merge sort 수행 과정

처음에 초기배열 상태에서 가운데를 기준으로 반으로 나누어 분할 상태가 된다.

이후 분할된 앞쪽과 뒷쪽을 각각 정렬(정복이라 칭함) 수행 후 다시 하나의 배열로 만드는 결합 과정을 수행하는 방식이다.

아래는 위키피디아에 나온 병합 정렬 과정의 수행 절차를 나타낸 것이다.

 

반응형

'프로그래밍' 카테고리의 다른 글

strcmp(), strtok()  (0) 2020.10.08
삽입정렬 (Insertion Sort)  (0) 2020.08.21
구글은 소프트웨어를 어떻게 테스트하는가?  (0) 2020.05.26
[C++] 디폴트 매개변수, default parameter  (0) 2019.08.14
bind error 방지  (0) 2010.07.17

+ Recent posts