병합정렬(Merge Sort)

[아이디어]

1. 정렬하고자 하는 데이터를 분할하되 원소가 하나만 남을 때까지 분할합니다.
   • 정렬할 데이터의 원소가 n개 있다고 할 때 n/2, n/2/2, n/2/2/2 ... 씩 분할해 가다가 원소가 하나만 남게 되는 경우 멈춥니다.
2. 1/2씩 데이터를 분할하였으므로 분할 된 두 데이터를 정렬하여 병합합니다.
   • 두 분할 데이터 각각의 가장 왼쪽 데이터 부터 비교해가며 작은 것이 앞에 오도록 정렬된 데이터로 병합합니다.
3. 2의 과정을 데이터 길이가 n이 될 때까지 반복하면 정렬이 완료됩니다.

[특징]

1. 평균 시간복잡도는 O(nlogn)입니다. 최악의 경우에도 O(nlogn)을 보장합니다.
2. 안정적인 시간복잡도를 보장하는 만큼 공간복잡도가 올라가는데, 병합정렬의 공간복잡도는 O(n)입니다.
3. 병합정렬은 안정정렬이므로 동일한 우선순위의 원소에 대해 정렬 전 순서와 정렬 후 순서가 보장됩니다.
   • 예를 들어 data = [3, 4, 1, 3]인 리스트를 정렬할 경우 그 결과는  [1, 3, 3, 4]가 되는데 이 때 data[1]에 저장된 3은 정렬 전 data[0]의 3이고 data[2]의 3은 정렬 전 data[3]의 3입니다.

[구현]

def merge_sort(data):
    data_len = len(data) 
    # 정렬할 데이터가 갯수 1개 이하인 경우 데이터를 그대로 리턴한다.
    if data_len <= 1:
        return data
    
    # 정렬할 데이터 갯수가 2개 이상인 경우 데이터를 인덱스 0부터 리스트 길이 // 2 - 1 까지 그리고
    # 리스트 길이 // 2 - 1부터 마지막 인덱스 까지로 이등분 하여 각각 재귀호출을 진행한다.
    # 재귀 호출이 완료된어 리턴된 값은 정렬된 부분 리스트이다.
    left_list = merge_sort(data[:data_len // 2])  # 정렬된 왼쪽 부분 리스트
    right_list = merge_sort(data[data_len // 2:])  # 정렬된 오른쪽 부분 리스트
    
    
    # 정렬된 두 개의 부분 리스트를 상호 비교해 가며 하나의 리스트로 합친다.
    l_list_idx = 0  # 정렬된 왼쪽 부분 리스트의 시작 인덱스
    r_list_idx = 0  # 정렬된 오른쪽 부분 리스트의 시작 인덱스
    data_idx = 0    # (부분 리스트가 합쳐질) 통합 리스트의 시작 인덱스
    
    # 왼쪽과 오른쪽 부분 리스트에 대한 탐색이 모두 완료되지 않았다면 
    while l_list_idx < len(left_list) and r_list_idx < len(right_list):
        # 왼쪽 리스트의 현재 요소와 오른쪽 리스트의 현재 요소를 비교한다.
        # 왼쪽 리스트의 현재 인덱스에 해당하는 값이 오른쪽 리스트의 현재 인덱스에 해당하는 값보다 작은 경우
        if left_list[l_list_idx] < right_list[r_list_idx]:
            # 왼쪽 리스트의 현재 인덱스 요소를 통합 리스트에 현재 인덱스에 넣어준다. 
            data[data_idx] = left_list[l_list_idx]
            # 왼쪽 리스트에서 데이터를 하나 추출 했으니, 왼쪽 리스트의 인덱스를 하나 증가 시킨다.
            l_list_idx += 1
        # 오른쪽 리스트의 현재 인덱스에 해당하는 값이 왼쪽 리스트의 현재 인덱스에 해당하는 값보다 작은 경우
        else:
            # 오른쪽 리스트의 현재 인덱스 요소를 통합 리스트에 현재 인덱스에 넣어준다.
            data[data_idx] = right_list[r_list_idx]
            # 오른쪽 리스트에서 데이터를 하나 추출 했으니, 오른쪽 리스트의 인덱스를 하나 증가 시킨다.
            r_list_idx += 1
        # 부분 리스트 중 하나를 골라 통합 리스트에 넣었으니, 통합 리스트의 인덱스를 하나 증가 시킨다.
        data_idx += 1
    
    # 오른쪽 부분 리스트에 해당하는 데이터들이 모두 정렬하는데 사용되었다면
    # 왼쪽 리스트의 나머지 요소들을 순차적으로 통합 리스트의 현재 인덱스 부터 복사해준다.
    if r_list_idx == len(right_list):
        while l_list_idx < len(left_list):
            data[data_idx] = left_list[l_list_idx]
            l_list_idx += 1
            data_idx += 1
    
    # 왼쪽 부분 리스트에 해당하는 데이터들이 모두 정렬된 상태라면
    # 오른쪽 부분 리스트의 나머지 요소들만 순차적으로 통합 리스트의 현재 인덱스 부터 복사해준다.
    while r_list_idx < len(right_list):
        data[data_idx] = right_list[r_list_idx]
        r_list_idx += 1
        data_idx += 1
    
    # 통합 리스트에 합병된 데이터는 정렬된 상태이므로 반환한다.
    return data