합병 정렬(Merge Sort)::자료구조

 합병 정렬은 주어진 array를 지속적으로 쪼개어 최소 array에서 값을 비교해 다시 합치고 정렬하는 방식으로 최소, 최대, 평균 시간 복잡도가 O(n*log n)으로 비교적 가장 빠른 정렬 방법입니다.

 

 쪼개진 array를 정렬하여 저장하기 위한 별도의 copy array가 필요하기 때문에 공간복잡도는 n입니다.

 

 자바와 벡터를 이용해 합병 정렬을 구현해 보겠습니다.

 

 

Java 코드

 

package sort;

import java.util.Vector;

public class MergeSort {

	static void merge(Vector<Integer> v, int s, int e, int m) {
		Vector<Integer> ret = new Vector<>();
		int i = s;
		int j = m + 1;

		while (i <= m || j <= e) {
			if (m < i)
				ret.add(v.get(j++));
			else if (e < j || v.get(i) < v.get(j))
				ret.add(v.get(i++));
			else
				ret.add(v.get(j++));
		}

		for (int k = s; k <= e; k++)
			v.set(k, ret.get(k - s));
	}

	static void mergeSort(Vector<Integer> v, int s, int e) {
		if (s < e) {
			int m = (s + e) / 2;

			mergeSort(v, s, m);
			mergeSort(v, m + 1, e);
			merge(v, s, e, m);
		}
	}

	public static void main(String[] args) {
		Vector<Integer> v = new Vector<>();

		v.add(20);
		v.add(112);
		v.add(403);
		v.add(52);
		v.add(70);
		v.add(6);
		v.add(33);
		v.add(45);
		v.add(50);
		v.add(7);
		v.add(61);
		v.add(33);

		System.out.println(v);
		mergeSort(v, 0, v.size() - 1);
		System.out.println(v);
	}

}

 

결과

 

[20, 112, 403, 52, 70, 6, 33, 45, 50, 7, 61, 33]
[6, 7, 20, 33, 33, 45, 50, 52, 61, 70, 112, 403]