MergeSort.java

package test;

import java.util.Arrays;

public class MergeSort {

	public static int[] sorted;
	
	public static void main(String[] args) {
//		int[] arr = {6, 3, 2, 7, 1, 5, 0, 9, 8, 4};
		int[] arr = new int[30];
		for(int i = 0 ; i < arr.length ; i++) {
			arr[i] = (int)(Math.random() * 101);
		}
		
		System.out.println(Arrays.toString(arr));
		System.out.println();
		
		sorted = new int[arr.length];
		
		mergeSort(arr, 0, arr.length - 1);
		mergeSortBottomUp(arr, 0, arr.length - 1);
		sorted = null;
		
		System.out.println();
		System.out.println(Arrays.toString(arr));
	}
	
	private static void mergeSort(int[] arr, int left, int right) {
		if(left == right) {
			System.out.println("[stop!] ▶ left : " + left + ", right : " + right);
			return;
		}
		
		int mid = (left + right) / 2;
		
		System.out.println("left : " + left + ", mid : " + mid + ", right : " + right);
		System.out.println();

		mergeSort(arr, left, mid);
		System.out.println();
		System.out.println("  left end ▷ left : " + left + ", mid : " + mid + ", right : " + right);
		System.out.println();
		mergeSort(arr, mid + 1, right);
		System.out.println();
		System.out.println("  right end ▷ left : " + left + ", mid : " + mid + ", right : " + right);
		System.out.println();

		merge(arr, left, mid, right);
	}
	
	private static void mergeSortBottomUp(int[] arr, int left, int right) {
		for(int size = 1; size <= right; size += size) {
			System.out.println("▶ size : " + size + ", left : " + left + ", right : " + right);

			for(int l = 0; l <= right - size; l += (2 * size)) {
				int low = l;
				int mid = l + size - 1;
				int high = Math.min(l + (2 * size) - 1, right);
				
				System.out.println("  ▷ low : " + low + ", mid : " + mid + ", high : " + high);
				merge(arr, low, mid, high);		// 병합작업
			}
		}
	}
	
	
	private static void merge(int[] arr, int left, int mid, int right) {
		System.out.println("    merge start!");
		System.out.println("      left : " + left + ", mid : " + mid + ", right : " + right);
		System.out.println("      before : " + Arrays.toString(arr));
		int l = left;
		int r = mid + 1;
		int idx = left;
		
		while(l <= mid && r <= right) {
			if(arr[l] <= arr[r]) {
				sorted[idx] = arr[l];
				idx++;
				l++;
			} else {
				sorted[idx] = arr[r];
				idx++;
				r++;
			}
		}
		
		if(l > mid) {
			while(r <= right) {
				sorted[idx] = arr[r];
				idx++;
				r++;
			}
		} else {
			while(l <= mid) {
				sorted[idx] = arr[l];
				idx++;
				l++;
			}
		}
		
		for(int i = left ; i <= right ; i++) {
			arr[i] = sorted[i];
		}
		System.out.println("      after : " + Arrays.toString(arr));
		System.out.println("      sorted : " + Arrays.toString(sorted));
		System.out.println("    merge end!");
		System.out.println();
	}
}