[Algorithm] merge sort

merge sort
O(NlogN)

부분 배열의 크기가 1이 될때까지 재귀를 통해 분할을 한다.

분할 후, 결합을 진행하되 부분 배열을 정렬하면서 결합하는 것이 특징이다.

- 분할(Divide) : 1개의 배열을 2개의 부분 배열로 나눈다.
- 정복(Conquer) : 부분 배열을 정렬한다.
- 결합(Combine) : 정렬된 부분 배열을 하나의 배열에 합병한다.

 

분할과 결합 과정이다.

결합 과정에서 정렬(정복)이 일어나는 과정을 보여주고 있다.

 

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());

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

            mergeSort(arr, 0, N-1);
            Arrays.stream(arr).forEach(System.out::println);
        } catch (Exception e) {
            System.out.println(e);
        }
    }

	// 분할
    static void mergeSort(int[] a, int left, int right){
        if(left==right) return; // 부분 배열의 크기가 1이 될때까지 분할한다.

        int mid = (left + right)/2;

		// 재귀를 통해 계속 분할을 한다.
        mergeSort(a, left, mid);
        mergeSort(a, mid+1, right);

		// 분할이 완료되면, 결합을 한다.
        merge(a, left, mid, right);
    }
	
    // 결합
    static void merge(int[] a, int left, int mid, int right){
        int l=left;     // 왼쪽 부분리스트의 시작점
        int r=mid+1;    // 오른쪽 부분리스트의 시작점
        int idx=left;   // 채워넣을 배열의 인덱스

        int[] sorted = new int[a.length];
        while(l<= mid && r <= right){
            if(a[l] <= a[r]){
                sorted[idx]=a[l];
                idx++; l++;
            }else{
                sorted[idx]=a[r];
                idx++; r++;
            }
        }

		// 부분 배열 중, 하나의 배열에 남은 데이터를 전부 결합한다.
        if(l > mid){
            while(r <= right){
                sorted[idx]=a[r];
                idx++; r++;
            }
        }else{
            while(l <= mid){
                sorted[idx]=a[l];
                idx++; l++;
            }
        }

		// 최종 정렬된 배열을 원본 배열에 넣는다.
        for(int i=left; i<=right; i++){
            a[i]=sorted[i];
        }
    }
}

---

정렬표 확인