참고문헌

Merge Sort

병합

  • 문제를 분할하고, 분할한 문제를 정복하여 합치는 과정
  • '분할 정복(Divide and Conquer)'
  • 정렬해야 할 리스트가 주어지면 해당 리스트를 분할을 반복하여 최대한 작게 쪼개진 시점에 부분리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식

병합정렬의 특징

  • '비교 정렬' : 데이터를 '비교'하면서 찾음
  • '제자리 정렬(in-place sort)이 아니다.' : 정렬의 대상이 되는 데이터 외에 추가적인 공간이 필요
  • '안정정렬(Stable Sort)' : 최대한 작게 문제를 쪼개어 앞의 부분리스트부터 차례대로 합쳐나감

과정

image

  1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할)

    • 여기서 주의할 점은, 합병정렬의 구현이 반드시 2개의 부분리스트로 나누어야 한다는 점은 아니다.
    • 어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이다.
    • 보통 아래와 같이 두 개의 부분리스트로 나누는 방식을 two-way 방식이라고 하니 참고하시면 좋을 듯 하다.

  2. 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다.

  3. 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복)

  • 각각의 부분리스트는 '정렬된 상태'여야 한다.
  • 그럼 어떻게 정렬을 할까?
    • 각 부분리스트의 첫 번째 원소부터 순차적으로 비교만 해주면 된다. (아래 이미지)
    • 각 부분리스트는 오름차순으로 정렬되어있기 때문에 앞부분부터 시작하여 하나씩 비교해주며 정렬해주면 된다.

image

image

장점

  1. 항상 두 부분리스트로 쪼개어 들어가기 때문에 최악의 경우에도 O(NlogN) 으로 유지가 된다.

  2. 안정정렬이다.

image

단점

  1. 정렬과정에서 추가적인 보조 배열 공간을 사용하기 때문에 메모리 사용량이 많다.

  2. 보조 배열에서 원본배열로 복사하는 과정은 매우 많은 시간을 소비하기 때문에 데이터가 많을경우 상대적으로 시간이 많이 소요된다.