merge sort in Python - Python 으로 merge sort 구현하기

Python 을 복습할 겸, 학부시절 재미있게 공부했던 merge sort 를 구현해보았다.

wikipedia 에 Pseudo code 가 있어서 쉽게 구현할 수 있었다.

다시한번 Python 언어가 얼마나 프로그램 알고리즘을 검증하는데 편한 언어인지 다시 한 번 알게 된 시간 이었다.

작성된 코드가 Pseudo code 와 거의 똑같다. 정말 최고다!

'''

Created on 2013. 3. 21.

@author: starblood

'''

def merge(left, right):

    result = []

    while len(left) > 0 or len(right) > 0:

        if len(left) > 0 and len(right) > 0:

            if left[0] <= right[0]:

                result.append(left[0])

                left = left[1:]

            else:

                result.append(right[0])

                right = right[1:]

        elif len(left) > 0:

            result.append(left[0])

            left = left[1:]

        elif len(right) > 0:

            result.append(right[0])

            right = right[1:]

    

    return result

def merge_sort(list):

    if len(list) <= 1:

        return list

    

    mid = len(list) / 2

    

    leftList = list[:mid]

    rightList = list[mid:]

    

    leftList = merge_sort(leftList)

    rightList = merge_sort(rightList)

    

    return merge(leftList, rightList)

''' Test code for sorting algorithm '''

list = [101, 5, -1, 20, 13, 11]

print list

newList = merge_sort(list)

print newList