Merge Sort

시간복잡도 O(N log N) 

 

최악의 경우에도 보장된다. 하지만 공간복잡도가 QickSort보다 두배크다.

 

package sasum;

public class myTest {
	private static void mergeSort(int[] arr) {
		int[] tmp = new int[arr.length];
		mergeSort(arr, tmp, 0, arr.length - 1);
	}

	private static void mergeSort(int[] arr, int[] tmp, int start, int end) {
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(arr, tmp, start, mid);
			mergeSort(arr, tmp, mid + 1, end);
			merge(arr, tmp, start, mid, end);
		}
	}

	private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {

		int i = start;
		int j = mid + 1;
		int k = start;

		while (i <= mid && j <= end) {
			if (arr[i] > arr[j]) {
				tmp[k++] = arr[j++];
			} else {
				tmp[k++] = arr[i++];
			}
		}
		
		if(i>mid) {
			while(j <= end) tmp[k++] = arr[j++];
		}else {
			while(i <= mid) tmp[k++] = arr[i++];
		}
		
		for(int n = start;n<=end;n++) arr[n] = tmp[n];

	}

	public static void main(String[] args) {
		int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
		mergeSort(arr);
		
		for(int a : arr) {
			System.out.print(a+" ,");
		}
		System.out.println();
	}
}