병합 정렬(merge sort)

배열을 더 이상 나눌 수 없을 만큼 작은 부분으로 분할한 다음, 이를 다시 병합하면서 정렬한다.

• 합병 정렬은 다음의 단계들로 이루어진다.
  • 분할(Divide): 주어진 배열을 크기가 같은 두 개의 하위 배열로 나눈다. 만약 배열의 크기가 홀수라면, 하나의 하위 배열이 나머지 하위 배열보다 원소가 한 개 더 많을 수 있다.
  • 정복(Conquer): 하위 배열을 재귀적으로 병합 정렬로 정렬한다.
  • 결합(Combine): 두 개의 정렬된 하위 배열을 병합하여 하나의 정렬된 배열로 만든다.

장점

• 안정적인 정렬 방법이다.
• 데이터의 크기가 커도, 일정한 시간 복잡도를 보장한다. $O({nlog(n)})$
• 이 일정한 시간 복잡도는, 평균 최악 최선의 경우 모두 동일하게 $O({nlog(n)})$이다.

단점

• 추가적인 메모리 공간이 필요하다. $O(n)$

예제

예제:
입력 배열: [38, 27, 43, 3, 9, 82, 10]

• 분할: [38, 27, 43] , [3, 9, 82, 10]
• 분할: [38], [27, 43] , [3, 9], [82, 10]
• 분할: [38], [27], [43] 등으로 더 이상 분할할 수 없을 때까지 계속한다다.
• 병합: [27, 38], [43], [3, 9], [10, 82]
• 병합: [27, 38, 43] , [3, 9, 10, 82]
• 병합: [3, 9, 10, 27, 38, 43, 82]

병합 정렬의 시간 복잡도

병합 정렬의 시간 복잡도를 이해하기 위해서는 병합 정렬의 두 주요 단계, 즉 "분할"과 "병합"을 살펴보아야 한다.

• 분할(Divide) 단계
  • 배열을 두 개의 부분 배열로 분할하는 작업은 O(1)의 시간 복잡도를 갖습니다. 그러나 이 분할을 배열이 원소 하나만 남을 때까지 계속 반복하게 된다.
  • 이 과정은 로그(log) 수준의 깊이로 이뤄집니다. 예를 들어, n개의 원소를 가진 배열을 2개씩 나눈다면 log(n)번의 단계를 거치게 된다.
  • 따라서, 분할 단계의 시간 복잡도는 $O(log n)$ 이다.
• 병합(Merge) 단계
  • 두 개의 정렬된 부분 배열을 병합하는 데에는 각 원소를 한 번씩만 확인하면 되므로, 이 작업의 시간 복잡도는 $O(n)$ 이다.
  • 그리고 병합 작업은 각 분할 단계마다 발생한다. 따라서 병합 작업의 전체 시간 복잡도는 $O(n log n)$ 이다.
  • 이 두 단계를 합치면 병합 정렬의 전체 시간 복잡도는 $O(n log n)$이 된다.

즉,
배열의 크기가 n일 때, 분할 단계에서 로그 시간에 해당하는 log(n) 단계가 있다.
각 단계에서는 n개의 원소 모두에 대해 작업을 수행한다 (병합).
따라서 전체 작업량은 $n (원소 수) × log(n) (분할 수)$이며, 이로 인해 시간 복잡도는 $O(n log n)$이 된다.

코드의 기본 틀

• 병합 함수(Merge Function)
  • 두 개의 정렬된 리스트를 받아서 하나의 정렬된 리스트로 병합하는 함수다.
• 병합 정렬 함수(Merge Sort Function)
  • 주어진 리스트를 반으로 분할한다.
  • 각 부분 리스트에 대해 재귀적으로 병합 정렬 함수를 호출한다.
  • 두 부분 리스트를 병합 함수를 사용하여 병합한다.

코드를 위한 연습

리스트 자르기

어떤 데이터 리스트가 있을 때, 리스트를 반으로 가르는 코드 작성하기.

리스트 슬라이싱을 활용해본다.

def split_list(data):
	mediam = int(len(data) / 2)
    left = data[:mediam]
    right = data[mediam:]
    return left, right

재귀용법 활용(mergesplit)

• mergesplit함수 만들기
  • 만약, 리스트 갯수가 한개이면 해당 값을 리턴한다.
  • 그렇지 않으면, 리스트를 두 개로 나눈다.
  • left = mergesplit(앞)
  • right = mergesplit(뒤)
  • merge(left, right)

merge함수 만들기