Merge sort(병합 정렬)

합병 정렬(merge sort) 알고리즘의 구체적인 개념

• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 합병 정렬은 다음의 단계들로 이루어진다.
• 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 합병 정렬의 과정
  추가적인 리스트가 필요하다.
  각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
  합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.

 

Python code

def merge(arr):
    lens = len(arr)
    ## 마지막 하나만 남았을때 더 이상 쪼갤 수 없으므로 리턴 및 재귀 종료
    if lens <= 1:
        return arr
    ## // 정수형 나누기 5//2 = 2
    mid = lens // 2
    ## 재귀 함수 리턴 될 때까지 분리 시켜줌
    left = merge(arr[:mid])
    right = merge(arr[mid:])
	## 배열은 크기가 정해져있어 리스트 호출
    result = list()
    ## 리스트의 몇번째 값을 의미함
    left_location, right_location = 0,0
	
    while len(left)>left_location and len(right) >right_location:
    ## 첫번째 정렬이 끝나고 항상 같은 리스트안에서는 왼쪽 값이 우측 값보다 작다 left[0],right[0]부터 비교
        if left[left_location]<right[right_location]:
            result.append(left[left_location])
            left_location += 1
        else:
            result.append(right[right_location])
            right_location += 1
	## 마지막 남은 더이상 비교되지 못하는 수를 넣어줌과 동시에 더 상위 재귀로 넘어가게 된다
    while len(left)>left_location:
        result.append(left[left_location])
        left_location += 1
    while len(right)>right_location:
        result.append(right[right_location])
        right_location += 1
    return result



pre = [6,8,3,9,10,1,2,4,7,5]
print(merge(pre))

merge sort