병합정렬

시간복잡도를 O(NlogN)을 보장한다

시간복잡도

BigO : O(NlogN)

구현

7 6 5 8 3 5 9 1
일단 반으로 나누고 나중에 합친다

import java.util.Arrays;

public class 병합정렬 {

	static int[] sorted = new int[8];
	static int num = 8;
	
	public static void main(String[] args) {
		int[] arr = {7,6,5,8,3,5,9,1};
		
		System.out.println(Arrays.toString(arr));
		mergeSort(arr);
		System.out.println(Arrays.toString(arr));
		
	}

	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) {
		for(int i = start; i <= end; i++) {
			tmp[i] = arr[i];
		}
		int part1 = start;
		int part2 = mid+1;
		int idx = start;
		while(part1 <= mid && part2 <= end) {
			if(tmp[part1] < tmp[part2]) {
				arr[idx] = tmp[part1];
				part1++;
			}else {
				arr[idx] = tmp[part2];
				part2++;
			}
			idx++;
		}
		for(int i=0; i<=mid-part1; i++) {
			arr[idx+i] = tmp[part1+i];
		}
	}
}