[컴][알고리즘] Merge sort

Merge sort / 머지 소트 / 정렬 알고리즘

목차

1. Insertion sort
2. quick sort
3. merge sort
4. heap sort

Merge sort

머지는 말그대로 합치는 것이다. 근데 이렇게 합칠 때 two finger algo 를 이용해 정렬을 하면서 합친다.

• http://www.youtube.com/watch?v=Kg4bqzAqRBM#t=1463 : MIT 알고리즘 강의
• Merge-sort-example-300px - Merge sort - Wikipedia : merge sort gif

얘는 quick sort 와의 차이는 이렇다.
퀵은 쪼개서 내려가면서 정렬을 한다.
머지는 쪼갠후에 다시 돌아오는 과정에서 머지를 한다.(top-down 과 bottom-up 방식이 있다.)

여기서는 top-down 방식을 이야기한다.

무엇을 합치느냐 하면 정렬하려는 리스트를 일단 낱개로 쪼갠다.
(이미 낱개니까 굳이 쪼개지 않아도 되지만 일단 쪼개진 상태라는 것을 잘 기억하자.)


이 쪼개진 녀석을 짝짓자.
처음에는 두개씩.
그리고 제자리를 찾아주자. 즉, 값이 큰 녀석을 오른쪽으로 두고, 작은 녀석을 왼쪽으로 두자.
그럼 이제 두개는 정렬이 끝났다. 그러면 이 "두개"를 다른 "두개"와 비교하자.
각각의 "두개"는 왼쪽에 가장 작은 값이 있다. 그래서 두 "두개"의 가장 왼쪽값을 비교한다.
"두개"중 더 작은 값을 왼쪽에 놓는다.
그리고 다시 남은 한개의 가장 작은 값과 나머지 "두개"의 가장 작은 값을 가지고 비교한다. 그리고 작은 값을 또 왼쪽에 놓는다.
이런식으로 반복해서 두 "두개"가 정렬돼서 합쳐진다.

그 다음은 당연히 8개를 가지고 한다.
그런데 그럴려면 당연히 다른 4개가 정렬되어 있어야 한다.
이렇기에 처음엔 두개, 다음엔 4개, 이런것을 구현하려면 거꾸로가 편하다

계속 나눠서 가장 작은 단위부터 merge sort 한다.
가장 작은 단위에 도달하면 Merge를 시작한다.
그리고 이 merge 한 결과를 return 해 준다.
그리고 이 return 한 결과 두개를 가지고 또 merge 한다.
이런식으로 최후에 merge 를 하면 된다.

Codes

from heapq import merge
 
def merge_sort(m):
    if len(m) <= 1:
        return m
 
    middle = len(m) / 2
    left = m[:middle]
    right = m[middle:]
 
    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

Source codes from : http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Python

Reference

1. http://en.wikipedia.org/wiki/Merge_sort