[알고리즘/정렬 알고리즘] 병합 정렬(Merge sort) Java, Python

병합 정렬(Merge sort) 알고리즘의 개념

• 병합 정렬(Merge sort)은 배열을 앞부분과 뒷부분을 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다
• 일반적인 방법으로 구현했을 때 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

병합 정렬(Merge sort) 알고리즘의 세부 과정

1. 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 부분 배열로 나눈다.
2. 나뉜 배열들을 다시 재귀적으로 병합 정렬을 이용해 정렬한다.
3. 두 부분 배열들을 다시 하나의 정렬된 배열로 합병한다.

병합 정렬(Merge sort) 예제

병합 정렬 Divide and Conquer 부분

 

Conquer 세부적인 모습

• 배열의 요소가 3, 4, 2, 1, 6, 8, 9, 5 순으로 저장돼있고 오름차순을 기준으로 정렬할 때 코드를 확인해보자

[Java 코드]

public class MergeSort {
    public static int[] buff;                    //임시 배열
    
    public static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int i;
            int center = (left + right) / 2;
            int p = 0;                            //임시 배열 인덱스
            int j = 0;
            int k = left;                        //원본 배열 인덱스
            
            mergeSort(arr, left, center);        //배열 앞부분 병합정렬
            mergeSort(arr, center+1, right);    //배열 뒷부분 병합정렬
            
            for(i = left; i <= center; i++) {    //임시 배열에 배열 앞부분을 넣어줌.
                buff[p++] = arr[i];
            }
            
            while(i <= right && j < p) {        //원본 배열의 뒷부분, 추가 배열의 앞부분의 원소끼리 비교한다.
                arr[k++] = buff[j] <= arr[i] ? buff[j++] : arr[i++]; 
            }
            
            while(j < p) {                        //임시 배열의 앞부분이 모두 커서 선택이 안됐다면 원본배열 뒷부분에 붙혀준다.
                arr[k++] = buff[j++];            //여기서 왜 i < right는 비교를 안할까? -> 비교를 하면서 선택을 못받은 잠재적 i값(큰 값)들은 원본배열 뒷부분에 있기 때문이다. 
            }
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {3, 4, 2, 1, 6, 8, 9, 5};
        int N = arr.length;
        buff = new int[N];
        
        mergeSort(arr, 0, N-1);
        
        for(int a : arr) {
            System.out.print(a+" ");
        }
 
    }
 
}

 

[Python 코드]

def merge_sort(divide_list):
    if len(divide_list) <= 1:
        return divide_list
 
    center = len(divide_list) // 2
    left = divide_list[:center]
    right = divide_list[center:]
 
    left_part = merge_sort(left)
    right_part = merge_sort(right)
    return merge(left_part, right_part)
 
 
def merge(left, right):
    i = 0
    j = 0
    conquer_list = []
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            conquer_list.append(left[i])
            i += 1
        else:
            conquer_list.append(right[j])
            j += 1
 
    while i < len(left):
        conquer_list.append(left[i])
        i += 1
 
    while j < len(right):
        conquer_list.append(right[j])
        j += 1
 
    return conquer_list
 
 
dac = [3, 4, 2, 1, 6, 8, 9, 5]
result = merge_sort(dac)
 
print(result)

 

References

• https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC  
• https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html