[파이썬] merge sort

def merge_sort(array):
    if len(array)<=1:
        return array
    
    midpoint=len(array)//2
    left, right=merge_sort(array[:midpoint]), merge_sort(array[midpoint:])
    return merge(left, right)

def merge(left, right):		# 정렬
    result=[]
    left_p=right_p=0		# 인덱스
    
    while left_p<len(left) and right_p<len(right):
        if left[left_p]<right[right_p]:
            result.append(left[left_p])
            left_p+=1
        else:
            result.append(right[right_p])
            right_p+=1
    
    # 나머지 값은 뒤에 이어붙임
    result.extend(left[left_p:])
    result.extend(right[right_p:])
    
    return result

def main():
    array=[5, 4, 3, 2, 1]
    print(array)
    
    result=merge_sort(array)
    print(result)
    
if __name__ == "__main__":
    main()

스캔된 문서.pdf

0.29MB

 

★ 실행 과정

1. array=[5, 4, 3, 2, 1]

midpoint=2

left=[5, 4]

right=[3, 2, 1]

 

2. array=[5, 4]

midpoint=1

left=[5]

right=[4]

merge()함수 실행 후 left=[4, 5]

 

3. array=[3, 2, 1]

midpoint=1

left=[3]

right=[2, 1]

merge()함수 실행 후 right=[1, 2, 3]

 

4. array=[5, 4, 3, 2, 1]

left=[4, 5]

right=[1, 2, 3]

merge()함수 실행 후 [1, 2, 3, 4, 5]

 

■ 알고리즘 설명

- 리스트가 길이가 1이 될 때까지 반씩 나누는 과정 반복.

- merge함수에 넣어서 오름차순 정렬한다.