병합정렬(MergeSort)

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
  
  
• 분할 정복 알고리즘 활용
  - 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최 종 결과를 얻어냄
  - top-down방식
  
  
• 시간복잡도 : O(nlogn)

구현코드

package array2;

import java.util.Arrays;

public class MergeSort {
	public static int[] a = {69,10,30,2,16,8,31,22};
	public static int[] s = new int[a.length];
	
	public static void merge(int left,int mid, int right) {
		int i = left;
		int j = mid + 1;
		int k = left;
		
		while(i <= mid && j <= right) {
			if(a[i] <= a[j]) s[k++] = a[i++];
			else 			 s[k++] = a[j++];
		}
		if(i>mid) for(int l=j; l<= right ; l++)  s[k++] = a[l];
		else      for(int l=i; l<= mid   ; l++)  s[k++] = a[l];
		
		for(int l = left; l<= right; l++) a[l] = s[l];
	}
	public static void mergesort(int left, int right) {
		if(left < right) {
			int mid = (left+right)/2;
			mergesort(left,mid);
			mergesort(mid+1,right);
			merge(left,mid,right);
			
			System.out.println(Arrays.toString(a));
		}
	}
	public static void main(String[] args) {
		System.out.println(Arrays.toString(a));
		mergesort(0, a.length-1);
	}
}

MergeSort(ArrayList)

package array1;

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

public class MergeSort {
	public static int[] a = { 69, 10, 30, 2, 16, 8, 31, 22 };
	public static int[] s = new int[a.length];

	public static List<Integer> merge(List<Integer> left, List<Integer> right) {
		List<Integer> r = new ArrayList<>();

		while (left.size() > 0 || right.size() > 0) {
			if (left.size() > 0 && right.size() > 0) {
				if (left.get(0) <= right.get(0))
					r.add(left.remove(0));
				else
					r.add(right.remove(0));
			} else if (left.size() > 0) {
				for (int i = 0; i < left.size(); i++)
					r.add(left.remove(0));

			} else if (right.size() > 0) {
				for (int i = 0; i < right.size(); i++)
					r.add(right.remove(0));
			}
		}
		return r;
	}

	public static List<Integer> mergesort(List<Integer> m) {
		if (m.size() == 1)
			return m;

		List<Integer> left = new ArrayList<>();
		List<Integer> right = new ArrayList<>();
		int mid = m.size() / 2;

		for (int i = 0; i < mid; i++)
			left.add(m.get(i));
		for (int i = mid; i < m.size(); i++)
			right.add(m.get(i));

		left = mergesort(left);
		right = mergesort(right);
		return merge(left, right);
	}

	public static void main(String[] args) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++) {
			list.add(a[i]);
		}
		System.out.println(list);
		System.out.println(mergesort(list));

	}
}