[알고리즘] 병합정렬(머지소트, Merge Sort)

1. 병합정렬이란?

재귀용법을 활용한 정렬 알고리즘이다.

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략인 분할 정복의 방법을 활용한 정렬 알고리즘.

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

2. 정렬 순서

3. 자바 코드 구현

package Concept;

import java.util.Arrays;
import java.util.Scanner;

public class MergeSortCode {
	
	public static void merge(int[] arr, int left, int mid, int right) {
		int i = left;
		int j = mid + 1;
		int t = 0;
		int[] temp = new int[arr.length];
		
		while (i <= mid && j <= right) {  // 왼쪽배열이랑 오른쪽배열 둘다 남아서 비교가 가능할 경우
			if (arr[i] <= arr[j]) {
				temp[t++] = arr[i++];
			} else {
				temp[t++] = arr[j++];
			}
		}
		while (i <= mid) { // 왼쪽 부분 배열이 남았을 경우
			temp[t++] = arr[i++]; // 왼쪽배열은 이미 정렬된 상태이므로 그대로 넣어줌.
		}
		
		while (j <= right) { // 오른쪽 부분 배열이 남았을 경우
			temp[t++] = arr[j++];
		}
		
		i = left;
		t = 0;
		while (i <= right) {
			arr[i++] = temp[t++]; //정렬된걸 다시 arr[]에 넣어줌.
		}
	}
	
	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, mid, right); // 왼쪽, 오른쪽 배열 합침.
		}
		
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] arr = new int[num];
		
		for (int i = 0; i < num; i++) {
			arr[i] = sc.nextInt();
		}
		
		mergeSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
}

4. 시간복잡도

n개의 배열을 정렬할 경우, n은 각각 2개의 n/2개로 나누어지고, 그것은 각각 4개의 n/4개로 나누어진다.

각 단계는 2^i * n / 2^i = O(n)이다.

단계는 항상 logn개 만큼 만들어지므로 O(logn)이다.

각 단계와 개수로 시간복잡도를 계산하면, O(n) * O(logn) = O(nlogn)이 된다.