[알고리즘] mergeSort 병합(합병)정렬 (pseudo-code, 파이썬, Java)

병합정렬(mergeSort)

• 주어진 크기가 n인 리스트 A를 크기가 n/2인 두 부분으로 나눈다.

• 크기가 n/2인 두 부분을 재귀적으로(recursively) 정렬한다.

• 정렬된 두 부분을 하나로 병합한다

  Merge(병합) 알고리즘 :

• 나뉜 두부분의 첫부분을 비교하여 작은 원소를 새로운 배열에 넣어주고, 작은 원소가 있던 부분배열의 인덱스를 늘려준다.

• 이렇게 부분배열이 다 넣어질 때까지 반복한다.

• 다른 한쪽부분은 남은 부분이 있을 수 있으므로 남은 부분배열의 전체를 배열에 넣어준다.

Pseudo-code

mergeSort 함수 : 정렬되지 않은 리스트(배열)을 재귀적으로 분할하는 역할을 한다

Algorithm mergeSort(arr, left, right)
   if (left < right) 
      mid = (first + right) / 2
      mergeSort(arr, left, mid)
      mergeSort(arr, mid+1, right)
      merge(arr, left, mid, right)

merge 함수 : 분할된 리스트(배열)을 병합(합병)하는 역할을 한다.

Algorithm merge(arr, left, right)
    i = 0 //left_list의 인덱스
    j = 0 //right_list의 인덱스
    k = 0 //merge_list의 인덱스
    while(i < len(left_list) and j < len(right_list))
        if left_list[i] <= right_list[j]
            merge_list[k] = left_list[i]
            i += 1
        else
            merge_list[k] = right_list[j]
            j += 1
        k+=1

    if (i < len(left_list))
        for i to len(left_list) - 1
            merge_list[k] = left_list[i]
            k += 1
    if (j < len(right_list))
        for j to len(right_list) - 1
            merge_list[k] = right_list[j]
            k += 1        

Python

리턴값 존재

def merge_sort(list):
    if len(list) <= 1:  # base case: 리스트에 원소가 하나 밖에 없을 때
        return list

    mid = len(list) // 2  # 리스트의 중간지점
    left_list = list[:mid]  # 리스트의 왼쪽 부분
    right_list = list[mid:]  # 리스트의 오른쪽 부분

    left_list = merge_sort(left_list)  # 재귀함수를 호출하여 다시 나눈다.
    right_list = merge_sort(right_list)

    return merge(left_list, right_list)  # 왼쪽부터 오른쪽으로 merge

def merge(left, right):
    i = 0
    j = 0
    merge_list = []

    while i < len(left) and j < len(right):  # left, right 가 아직 남아있을 때
        if right[j] < left[i]:
            merge_list.append(right[j])
            j += 1
        else:
            merge_list.append(left[i])
            i += 1

    if (i < len(left)):  # left 만 남아있을 때, 리스트에 리스트를 합친다.
        merge_list += left[i:len(left)]
    else:
        merge_list += right[j:len(right)]

    return merge_list

Java

public class MergeSort{
    public void mergeSort(int[] arr, int left, int right){
        if(left < right){
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right)

            merge(arr, left, mid, right)
        }
    }
     public void merge(int[] arr, int left, int mid, int right){
       //두 부분배열의 사이즈 찾기
        int n1 = mid - left + 1 ;
        int n2 = right - mid;

        //mid를 기준으로한 부분배열
        int left_list[] = new int[n1];
        int right_list[] = new int[n2];

        //배열값 넣기
        for (int i = 0; i < n1; i++) {
            left_list[i]  = arr[left + i];
        }

        for (int j = 0; j < n2; j++) {
            right_list[j] = arr[mid + 1 + j];
        }

        //merge
        //초기 인덱스
        int i = 0;
        int j = 0;

        // 병합된 배열의 초기 인덱스
        int k = left;

        // L 사이즈만 큼 loop (L배열 초기 인덱스 < L배열 사이즈)
        // R 사이즈만 큼 loop (R배열 초기 인덱스 < R배열 사이즈)  
        while (i < n1 && j < n2) {
            // L 배열의 값 <= R배열의 값
            if (L[i] <= R[j]) {
                // L값 arr에 담아주기
                arr[k] = L[i];
                //L 을 담아주었으니 L의 인덱스 증가
                i++;
            }else {
                // L 배열의 값 > R배열의 값
                // R값 arr에 담아주기
                arr[k] = R[j];
                //R 을 담아주었으니 R의 인덱스 증가
                j++;
            }
            k++;
        }

        //L에 남은 값이 있다면 복사
        while(i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        //R에 남은 값이 있다면 복사  
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

수행시간분석

T(n) = 1 (if n == 1)

​ = 2T(n/2) + cn (if n > 1)

​ (c는 상수)

T(n/2) = 2T(n/2^2) + cn/2

T(n) = 2(2T(n/2^2) + cn/2) + cn = 2^2(T(n/2^2)) + cn + cn

...

T(n) = 2^k(T(n/2^k)) + kcn

n/2^k = 1
k = log n 일 때,

T(n) = nT(1) + cnlog n

T(n) = O(nlog n)