병합 정렬(Merge Sort)

병합 정렬

- 분할 정복 (divide & conquer) 방법을 이용한 알고리즘

- 퀵 정렬과 유사하나 차이점은 안정 정렬에 속하며 균등분할을 하는 것이 차이가 있음.

- 퀵 정렬은 정렬 후 분할한다면, 병합 정렬은 분할 후 합치면서 정렬함.

 

정렬 방법

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

1. 배열의 길이가 0 또는 1 일때 까지 분할(divide)함.

2. 더 이상 분할 할 수 없을 때, 병합(merge)을 시작함.

3. 분할한 두개의 배열을 순차적으로 합치는데, 합칠때 두 배열 중에서 작은 값을 찾아서 하나씩 배열에 교체해 나감. (오름차순 기준)

4. 왼쪽 배열 값과 오른쪽 배열의 값을 비교해서 작은 값을 찾아서 원본 배열값에 교체.

 

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.IntStream;

public class MergeSort {
    public static void merge(int arr[], int left, int right) {
        int[] L = Arrays.copyOfRange(arr, left, (left+right)/2);
        int[] R = Arrays.copyOfRange(arr,(left+right)/2, right);

        int i=0,j=0,idx=left;
        while (i < L.length && j < R.length) {
            if(L[i] < R[j]) {
                arr[idx++] = L[i++];
            } else {
                arr[idx++] = R[j++];
            }
        }

        while (i < L.length) {
            arr[idx++] = L[i++];
        }

        while (j < R.length) {
            arr[idx++] = R[j++];
        }
    }

    public static void divide(int arr[], int left, int right) {
        if (Math.abs(right-left) <= 1) {
            return;
        }

        divide(arr, left, (left + right) / 2);
        divide(arr, (left + right) / 2, right);
        merge(arr, left, right);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int _loop = Integer.parseInt(br.readLine());

        int arr[] = new int[_loop];
        for (int i = 0; i < _loop; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();

        divide(arr,0,arr.length);
        
        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::println);
        System.out.println();
    }
}