병합 정렬 (Merge Sort)

1. 개요

• 분할 정복 전략을 사용한다.
• 배열을 절반씩 분할하고 정렬한다.
• 정렬된 부분 배열을 하나로 병합한다.
• 부분 배열에 추가적인 메모리를 할당한다.

---

2. 특징

• 속도가 빠르다.
• 안정 정렬이다.
• 시간복잡도: O(NLogN)
• 순차적인 비교를 하기 때문에 연결 리스트에서 사용하기 좋다.
• 용량이 큰 데이터를 정렬할 때, 메모리 문제가 발생할 수 있다.

---

3. 코드

import java.util.Arrays;

public class MergeSortTest {

	public static void main(String[] args) {
		int[] nums = { 3, 2, 7, 5, 11, 12, 1 };

		mergeSort(nums, 0, nums.length - 1);

		System.out.println(Arrays.toString(nums));
	}

	private static void mergeSort(int[] arr, int left, int right) {
		if (left >= right) {
			return;
		}

		int mid = (left + right) / 2;

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

	private static 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;

		while (i < L.length && j < R.length) {
			if (L[i] <= R[j]) {
				arr[k++] = L[i++];
			} else {
				arr[k++] = R[j++];
			}
		}

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

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

}