[알고리즘]합병 정렬(Merge Sort)

Goal

• 합병 정렬에 대해 설명할 수 있다.
• 합병 정렬 과정에 대해 설명할 수 있다.
• 합병 정렬을 구현할 수 있다.
• 합병 정렬의 시간복잡도와 공간복잡도를 계산할 수 있다.

Abstract

• 병합 정렬이라고도 부르며, 분할 정복 방법에 근거한 정렬 알고리즘이다.
• 퀵 정렬 방법과는 반대로 안정 정렬에 속한다.
• 요소를 나눈 후 다시 합병시키면서 정렬해나가는 방식으로, 나누는 방식은 퀵 정렬과 유사하다.

Code

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);
    }
}

void merge(int[] arr, int left, int mid, int right) {
	int[] L = Arrays.copyOfRange(arr, left, mid + 1);
    int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);
	
    int i = 0;
    int j = 0;
    int k = left;
    
    int ll = L.length;
    int rl = R.length;
    
    while(i < ll && j < rl) {
    	if(L[i] <= R[j]) {
     		arr[k] = L[i++];   
        }else {
        	arr[k] = R[j++];
        }
        
        k++;
    }
    
    while(i < ll) {
    	arr[k++] = L[i++];
    }
    while(j < rl) {
    	arr[k++] = R[j++];
    }
}

합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수 있다.

[전체코드]

import java.util.*;
import java.io.*;
class Main {
    public static void main(String args[]) {
        int[] array = {230, 10, 60, 550, 40, 220, 20};
        mergeSort(array, 0, array.length - 1);

        for (int v: array) {
            System.out.println(v);
        }
    }
    
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int[] L = Arrays.copyOfRange(array, left, mid + 1);
        int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);

        int i = 0, j = 0, k = left;
        int ll = L.length, rl = R.length;

        while (i < ll && j < rl) {
            if (L[i] <= R[j]) {
                array[k] = L[i++];
            } else {
                array[k] = R[j++];
            }
            k++;
        }

        while (i < ll) {
            array[k++] = L[i++];
        }

        while (j < rl) {
            array[k++] = R[j++];
        }
    }
}