병합 정렬(Merge Sort)

Intro::

병합정렬에 대해 알아보자.

정의

퀵소트와 함께 많이 언급되는 정렬 방식이다. 퀵소트와는 반대로 안정 정렬에 속한다.

1. 요소를 쪼갠다.

2. 비교 후 합친다.

3. 합쳐진 요소들 끼리 또 합친다.(이때는 두 요소가 오름차순으로 정렬되어있음)

시간복잡도

O(nlogn)

코드

package algorithm;

import java.util.Arrays;

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

		int i = 0, j = 0;

		while (i < L.length && j < R.length) {
			arr[left] = L[i] <= R[j] ? L[i++] : R[j++];
			left++;
		}

		// remain
		while (i < L.length) {
			arr[left++] = L[i++];
		}
		while (j < R.length) {
			arr[left++] = R[j++];
		}
	}
	public static 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, right);
			System.out.println(Arrays.toString(arr));
		}
	}

	public static void main(String[] args) {
		int[] arr = {6, 1, 3, 5, 2, 4};
		mergeSort(arr, 0, arr.length - 1);
	}
}

/*
[6, 1, 3, 5, 2, 4]

[1, 6, 3, 5, 2, 4]
[1, 3, 6, 5, 2, 4]
[1, 3, 6, 2, 5, 4]
[1, 3, 6, 2, 4, 5]
[1, 2, 3, 4, 5, 6]
*/

References::