[코딩 + 알고리즘 완주반] 18일차. 병합정렬 (merge sort)

# 병합 정렬

재귀 용법을 사용한 정렬 알고리즘

리스트를 반으로 잘라 나눈 후 재귀적으로 병합 정렬 

부분 리스트를 다시 하나의 정렬된 리스트로 합병

 

# 알고리즘 구현

# 병합하기
def merge(left,right):
	lp = 0
    rp = 0
    merged=list()
    
    # left,right 둘다 데이터 있을 때
    while len(left) >lp and len(right) >rp :
    	if left[lp]>right[rp]:
    		merged.append(right[rp])
        	rp+=1
    	else:
    		merged.append(left[lp])
        	lp+=1
            
     # left에만 데이터 남아있을 때
     while len(left) > lp :
     	merged.append(left[lp])
        lp+=1
        
     # right에만 데이터 남아있을 때
     while len(right) > rp :
     	merged.append(right[rp])
        rp+=
     return merged

# 데이터 나누고 merge 함수 호출
def mergesplit(data):
	if len(data) <=1:
    	return data
    medium = int(len(data)/2)
    left = mergesplit(data[:medium]
    right = merghsplit(data[medium:]
    return merge(left,right)
 

# 시간복잡도

단계는 항상

logn개 만들어짐각 단계의 시간 복잡도는 O(n)

 전체 시간 복잡도는  O(nlogn)