[알고리즘] Merge Sort

Merge Sort

개념

• 재귀용법을 활용하여 재귀적으로 리스트를 절반으로 자른 후 데이터를 순서에 맞게 합쳐가며 정렬하는 방법이다.
  1. 데이터를 절반으로 나눈다. (Recursive하게 반복)
  2. 두개로 나눠진 list의 가장 앞에 위치한 데이터들을 비교후 가장 작은 데이터를 새로운 빈 리스트에 추가를 하며 정렬된 하나의 리스트를 만든다.
  3. 분할정복으로 계속 데이터를 쪼개고 합치며 하나의 정렬된 리스트를 만든다.
• 분할 정복(Divide and Conquer) 알고리즘이다.
• 평균과 최악의 시간복잡도는 O(nlog n)이다.

예시

사진출처: https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

Java 구현 코드

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer[] arr = {3,8,43,20,9,15,61,54,13,94,2,10};
		
		List<Integer> list = new ArrayList<>(Arrays.asList(arr));
		
		System.out.println(split(list).toString());
	}
	
	
	// Recursive하게 List를 절반으로 나눠주고 다시 병합해준다.
	public static List<Integer> split(List<Integer> list){
		if (list.size() <= 1)
			return list;
		
		int listSize = list.size();
		List<Integer> left = list.subList(0, listSize/2);
		List<Integer> right = list.subList(listSize/2, listSize);
			
		left = split(left);
		right = split(right);
		return merge(left, right);
	}
	
	
	
	// 2개의 list를 앞의 수를 계속 비교해가며 작은 수부터 merged list에 넣어 정렬하며 합친다.
	public static List<Integer> merge(List<Integer> left, List<Integer> right){
		// left, right가 둘 다 있을 때
		int leftPoint = 0;
		int rightPoint = 0;
		List<Integer> merged = new ArrayList<>();
		while(left.size() > leftPoint && right.size() > rightPoint) {
			if(left.get(leftPoint) < right.get(rightPoint)) {
				merged.add(left.get(leftPoint));
				leftPoint++;
			}
			else {
				merged.add(right.get(rightPoint));
				rightPoint++;
			}
		}
		
		// left가 없을 때
		while (left.size() > leftPoint) {
			merged.add(left.get(leftPoint));
			leftPoint++;
		}
		
		// right가 없을 때
		while (right.size() > rightPoint) {
			merged.add(right.get(rightPoint));
			rightPoint++;
		}
		
		return merged;
	}

}