합병 정렬 (Merge sort)

정의

 합병 정렬 또는 병합 정렬 (merge sort)는 O(nlogn) 비교 기반 정렬 알고리즘이다. 이 정렬은 분할 정복 알고리즘의 하나로, 존 폰 노이만이 1945년에 개발했다.

* 비교 정렬은 하나의 추상적인 비교 동작을 통해 목록 요소들을 읽어내는 정렬 알고리즘의 일종으로, 두 요소 중 어느 것이 최종 정렬 목록에 발생되어야 하는지를 결정한다. 

알고리즘

1. 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는

2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

소스코드

def mergeSort(X) :

  if len(X) <= 1 :
    return X

  left = mergeSort(A[:len(A)/2])
  right = mergeSort(A[len(A)/2:])

  i, j, k = 0, 0, 0
  while i < len(left) and j < len(right) :

       if left[i] < right[j] :
           A[k] = left[i]
           i += 1
       else:
           A[k] = right[j]
           j += 1
       k += 1

      if i == len(left) :
          while j < len(right) :
             A[k] = right[j]
             j += 1
             k += 1
       elif j == len(right) :
          while i < len(left) :
             A[k] = left[i]
             i += 1
             k += 1
  return A

출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC