[Algorithm] 합병정렬(merge sort)

✨ 합병정렬(merge sort)

합병 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
(분할정복:그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법)

 

✨ 과정(2-way 합병 정렬)

1. 길이가 1이하임을 확인(1이하인경우 정렬완료상태)
2. 분할: 리스트를 절반으로 나눈다.
3. 정복:각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬
4. 결합:두 부분 리스트를 다시 하나의 정렬된 리스트로 합병( 임시배열에 저장 )
5. 복사:임시 배열에 저장된 결과를 원래 배열에 복사

def merge_sort(arr):
    #길이 1이하확인
    if(arr<=1):return arr

    #분할
    low_arr=merge_sort(arr[:len(arr)//2])
    high_arr=merge_sort(arr[len(arr)//2:])
    
    merged_arr = []
    l = h = 0
    #어느 한쪽이 전부 merged_arr에 들어가면 끝
    while l < len(low_arr) and h < len(high_arr): 
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    
    #정렬하고 남은 arr는 정렬된 상태이므로 merged_arr 에 이어서 추가
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

https://www.daleseo.com/sort-merge/