[알고리즘 정리] Merge Sort ( 병합정렬 ) - O(NlogN), 추가메모리, Stable

🤔Merge Sort(병합정렬) 이란 ?

병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘

💡 과정

1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할) → mergeSort() 메소드
2. 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다. → if (start == end) return;
3. 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복) → merge() 메소드

⚡ 특징

• 시간 복잡도 : 최선, 평균, 최악 모두 $O(NlogN)$
• 데이터를 “비교”하면서 찾기 때문에 비교정렬
• 추가 메모리 필요 하기 때문에 제자리 정렬이 아니다.
• Stable한 정렬

---

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n; // 배열의 길이를 저장하는 변수
    static int sortedArr[]; // 정렬된 배열을 저장할 변수

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

        n = Integer.parseInt(br.readLine());

        // 정렬할 배열 입력
        int arr[] = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }


        sortedArr = new int[n];
        mergesort(arr, 0, n - 1);


    }




    // Merge Sort를 수행하는 메서드
    private static void mergesort(int arr[], int start, int end) {
        // Base Case: 부분 배열의 크기가 1인 경우, 이미 정렬된 상태이므로 종료
        if (start == end)
            return;

        // 부분 배열을 중간 지점에서 나누기
        int mid = (start + end) / 2;


        mergesort(arr, start, mid);    // 왼쪽 부분 배열을 재귀적으로 정렬
        mergesort(arr, mid + 1, end);  // 오른쪽 부분 배열을 재귀적으로 정렬


        // 정렬된 부분 배열을 병합
        merge(arr, start, mid, end);
    }






    // 두 부분 배열을 병합하는 메서드
    private static void merge(int arr[], int start, int mid, int end) {
        // 왼쪽 부분리스트의 시작점, 오른쪽 부분리스트의 시작점, 채워 넣을 배열의 인덱스 초기화
        int left = start;
        int right = mid + 1;
        int idx = left;



        // 두 부분 배열을 비교하면서 병합
        while (left <= mid && right <= end) {
            if (arr[left] <= arr[right]) {
                sortedArr[idx] = arr[left];
                idx++;
                left++;
            } else {
                sortedArr[idx] = arr[right];
                idx++;
                right++;
            }
        }


        while (left <= mid) {      // 왼쪽 부분리스트에 남아있는 원소들을 복사
            sortedArr[idx] = arr[left];
            idx++;
            left++;
        }

        while (right <= end) {     // 오른쪽 부분리스트에 남아있는 원소들을 복사
            sortedArr[idx] = arr[right];
            idx++;
            right++;
        }



        // 정렬된 부분 배열을 원래 배열에 복사
        for (int i = start; i <= end; i++) {
            arr[i] = sortedArr[i];
        }
    }
}