[알고리즘] 정렬 : 합병 정렬

합병 정렬은 분할 정복 알고리즘을 활용한 정렬 방법이다. 먼저 원소들을 반으로 나누고 두 개의 부분 배열을 비교하여 정렬된 상태로 만들어 가는 것이다.

---

개념

• 오름차순 기준으로 설명한다.
• N개의 원소가 있을 때 N//2를 기준으로 원소들을 반으로 나눈 값을 인덱스로 하고
• 위에서 구한 인덱스를 기준으로 리스트를 반으로 나눈다.
• 반으로 나눈 리스트를 또 다시 반으로 나누고 리스트 원소의 개수가 1일 때 해당 원소를 반환한다.
• 이렇게 반으로 나눈 원소들을 합쳐 나간다.
• 초기에 1개의 원소들로 이루어진 리스트를 비교하여 정렬 후에 2개의 원소를 갖는 리스트로 만든다.
• 이후에는 2개의 원소를 갖는 리스트끼리 비교하여 정렬하여 4개의 원소를 갖는 리스트로 만든다.
• 위의 과정을 반복하는 것이 합병 정렬이다.

구현

•  merge_sort 함수는 최종적으로 정렬된 리스트를 반환한다.
• 함수 내에서 전달받은 numbers를 기준으로 반으로 나눈다.
• 반으로 나눈 리스트를 다시 merge_sort로 전달하여 반으로 나눈다.
• 이때 numbers가 한 개의 원소를 갖을 때를 기저 사례로 설정한다.
• 이제는 merge 함수에 전달하여 정렬된 리스트로 반환하도록 한다.

def merge_sort(numbers):
    if len(numbers) < 2:
        return numbers
    mid = len(numbers) // 2
    left_numbers = numbers[:mid]
    right_numbers = numbers[mid:]
    left_numbers = merge_sort(left_numbers)
    right_numbers = merge_sort(right_numbers)

    return merge(left_numbers, right_numbers)

• 두 개의 리스트를 전달받는다.
• 두 개의 리스트에서 각각 첫 번째 원소들을 비교하여 더 작은 수를 result에 추가한다.
• 만약 한 쪽의 리스트를 모두 result에 추가했다면 다른 쪽의 리스트의 원소들을 result에 순차적으로 추가한다.
• 이 과정을 통해 정렬된 상태를 반환할 수 있게 된다.

def merge(left_numbers, right_numbers):
    result = []
    while left_numbers or right_numbers:
        if left_numbers and right_numbers:
            if left_numbers[0] < right_numbers[0]:
                result.append(left_numbers[0])
                left_numbers = left_numbers[1:]
            else:
                result.append(right_numbers[0])
                right_numbers = right_numbers[1:]
        elif left_numbers:
            result.append(left_numbers[0])
            left_numbers = left_numbers[1:]
        elif right_numbers:
            result.append(right_numbers[0])
            right_numbers = right_numbers[1:]
    return result

 

특징

• 입력 데이터와 관계없이 정렬되는 시간이 동일한다.
• 정렬해야 할 데이터가 클 경우에는 이동 횟수가 많아지기 때문에 시간적 낭비가 발생한다.

시간 복잡도

리스트 내에 원소가 한 개 남을 때까지 분할 할 때 N번 재귀 호출이 발생하며 리스트를 반씩 정렬하면서 합쳐지기 때문에 logN의 시간이 발생한다. 따라서 NlogN만큼의 시간이 소요된다.