Python으로 구현한 Merge Sort

분할정복 (Divide & Conquer) 기법을 이용하여 정렬한다.

주어진 리스트를 원소의 갯수가 1인 리스트가 될 때까지 분할한 뒤 그 리스트들을 다시 합치는 과정에서 원소를 비교하여 정렬을 수행한다.

소스코드

vi sort.py

# Merge Sort
def sort_merge(arr):

    if len(arr)<=1: return arr ## Exception

    ## Divide
    left    = sort_merge(arr[:len(arr)//2])
    right   = sort_merge(arr[len(arr)//2:])

    ## Conquer
    i,j,k = 0,0,0
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:   arr[k],i = left[i],i+1
        else:                   arr[k],j = right[j],j+1
        k += 1
    while k<len(arr):
        if i==len(left):    arr[k],j = right[j],j+1
        elif j==len(right): arr[k],i = left[i],i+1
        k += 1

    return arr 

테스트 코드

vi test_sort.py

#!/bin/python

def main():
    import random
    import sort
    A=[random.randint(1,100) for _ in range(10)]
    print(A)
    print(sort.sort_merge(A))

if __name__ == '__main__':
    main()

수행 결과

$ python test_sort.py 
[68, 70, 54, 30, 26, 96, 52, 90, 88, 11]
[11, 26, 30, 52, 54, 68, 70, 88, 90, 96]