알고리즘 [합병정렬]

🔎 분할통치법

분할 통치법: 알고리즘 설계 기법의 일종으로 세가지 형태로 나뉘게 된다.

1. 분할 : 입력된 데이터를 둘 이상의 분리된 부분집합으로 나눈다.
2. 재귀 : 각각에 대한 부문제를 재귀적으로 해결한다.
3. 통치 : 부문제들에 대한 해결을 합쳐 L의 해결을 구한다.

분할 통치법으로 설계한 정렬 형태 : 합병정렬, 퀵 정렬

🔎 합병 정렬

특징

1. 분할통치법에 기초한 정렬
2. 비교에 기초한 정렬
3. 외부의 우선순위 큐를 사용하지 않음
4. 데이터를 순차적으로 접근한다.

Alg mergeSort(L)
  input list L with n elements
  output sorted list L

1. if(L.size() > 1)
  L1, L2 <- partition(L, n/2) 
  mergeSort(L1)
  mergeSort(L2)
  L <- merge(L1,L2)
2. return

Alg merge(L1,L2)
  input sorted list L1 and L2 with n/2 elements each
  output sorted list of L1 U L2

1. L <- empty list
2. while (!L1.isEmpty() & !L2.isEmpty())
  if(L1.get(1) <= L2.get(1))
    L.addLast(L1.removeFirst())
  else
    L.addLast(L2.removeFirst())
3. while (!L1.isEmpty())
  L.addLast(!L2.isEmpty())
4. while (!L2.isEmpty())
  L.addLast(L2.removeFirst())
5. return L

1에서 빈 리스트를 만들고 해당 나눠진 두가지 리스트의 값을 비교하여 차례대로 넣어주고 남은 리스트는 뒤에 붙여준다.

의사코드로 보니 훨씬 간단하고 이해가 잘 된다.