Merge Sort

본 문서는 2021년 12월 28일 에 작성되었습니다.

Merge Sort 는 데이터 집합의 규모가 커질수록 기하급수적으로 성능우위를 점할 수 있습니다.
그러나 이를 구현하기 위해서는 Merge 에 대한 이해도가 필요하며 구현 난이도는 높은 편입니다.

Merge Sort 란?

Merge Sort(오름차순) 은 Merge Procedure 을 재귀적으로 호출하는 개념입니다.
Merge Procedure 는 다음의 3단계로 구성되어 있습니다.

1. 분할 | A{1,2, ... , n} 을 n/2 개씩 분할 수열 L, R로 분할
2. 정복 | Merge 실행
3. 결합 | L, R 을 A' 로 병합

Merge Sort 는 다음과 같이 구성되어 있습니다.

1. 분할 | A{1,2, ... , n} 을 n/2 개 씩 분할 수열 L, R로 분할
   1.1. 종료 | 길이가 1인 기초 배열이 나올 때까지 분할

2. 정복 | Merge 실행

3. 결합 | 병합
   3.3. 2와 3은 각각의 분할 수열을 하나의 A' 로 병합하는 일련의 과정을 통칭한다.

쉽게 표현하자면 데이터 집합인 배열을 끝없이 분할하여 기초배열로 만들고
기초배열 단계에서 부터 2개의 배열이 좌, 우로 갈지 판별해서 새로운 배열로 병합한다는 것이다.

이를 의사코드로 확인해보면 다음과 같습니다.

# Merge Procedure 의사코드

Merge Procedure (A:길이 n의 수열, pqr 인덱스(p<=q<r))

n1=q-p+1
n2=r-q
배열 L[1, ... , n+1] 과 R[1, ... , n2+1] 을 생성한다.

for i=1 to n1
   L[i]=A[p+i-1] // 배열 복사

for j=1 to n2
   R[j]=A[q+j] // 배열복사
   
L[n1+1]="특정값" // 경계값 설정
L[n2+1]="특정값" // 경계값 설정

i=1
j=1
for k=p to r
   if L[i] <= R[j]
      A[k]=L[i]
      i=i+1
   else A[k]=R[j]
      j=j+1

# Merge Sort 의사코드

Merge Sort
if p<r
   Merge Sort (A.p.q)
   Merge Sort (A.q=1.r)
   Merge (A.p.q.r)

Java 에서 적용하려면?

기본적인 배열의 형태를 유지한다는 전제가 있다면 다음의 선택지가 있습니다.

1. ArrayList 구조 사용 (사실상 일반 배열)
2. LinkedList 구조 사용

# ArrayList + Merge Sort 분석

기본적으로 Merge Sort 는
분할정복정렬 과정에 임시배열이 필요하므로 공간 낭비가 발생한다.

또한 정렬할 데이터 집합의 단일 레코드 크기가 크면 시간 낭비가 발생할 수 있다.

단, 결국 새로운 배열을 만들고 없애는 방식이기 때문에,
ArrayList 의 단점인 삽입, 삭제의 문제점은 가려지게 된다.
ArrayList 의 기본단점이 가려져도 Merge Sort 의 단점은 남아있어서 추천하지 않는다.

# LinkedList + Merge Sort 분석

LinkedList 는 Node 라는 것을 이용하여 서로 개별적인 공간들을 연결하는 개념이다.

따라서 LinkedList 로 Merge Sort 를 구현하면 Node 만 변경하면 되므로,
분할정복정렬 과정에 임시 배열이 필요 없어지게 되어 제자리 정렬 이 된다.

따라서 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적 이게 된다.

분석

0. 안정성 : 보장
1. 최적 상황 : O(n log n)
2. 평균 상황 : O(n log n)
3. 최악 상황 : O(n log n)
4. 공간복잡도 : O(n) // 임시변수 정도의 공간만 할당됨

Ref

[알고리즘] 합병정렬이란?
Merge Sort - The Sorting Algorithm Family Reunion