Merge sort

머지 소트의 기본 개념은 Divide and Quanqer 알고리즘이다.

리스트를 소트된 순서대로 쪼개가면서(1개의 엘리멘트가 나올때까지) 짜른 다음
두개의 리스트를 하나로 순서대로 합해가면서 소팅을 한다.

* 간단하게 파이슨으로 머지소트를 구현해 보면 다음과 같다.

     1 def mergesoft(list):
     2     if len(list) <= 1:
     3         return list
     4        
     5     middle = len(list) / 2
     6     left = []
     7     right = []
     8     index = 0
     9     for item in list:
    10         if index < middle:
    11             left.append(item)
    12         else:
    13             right.append(item)
    14         index += 1
    15        
    16     left = mergesoft(left)
    17     right = mergesoft(right)
    18     result = merge(left,right)
    19     return result
    20    
    21 def merge(left,right):
    22     result = []
    23     while len(left) > 0 and len(right) > 0:
    24         if left[0] <= right[0]:
    25             result.append(left.pop(0))
    26         else:
    27             result.append(right.pop(0))
    28     if len(left) > 0:
    29         for item in left:
    30             result.append(item)
    31     if len(right) > 0:
    32         for item in right:
    33             result.append(item)
    34     return result