합병정렬 알고리즘 (Merge Sort)

Main.java

/**
 * 합병정렬 알고리즘 (Merge Sort)
 * 
 * @author devetude
 */
public class Main {
	public static void main(String args[]) {
		int[] arr = { 9, 3, 1, 2, 8, 6, 5, 7, 4 };
		mergeSort(arr);

		for (int item : arr) {
			System.out.print(item + " ");
		}
	}

	private static void mergeSort(int[] arr) {
		int len = arr.length;

		if (len == 1) {
			return;
		}

		else {
			int mid = len / 2;
			int[] leftArr = new int[mid];
			int[] rightArr = new int[len - mid];

			// 중간을 기준으로 왼쪽 배열을 생성 (Create Left Array Based On Middle)
			for (int i = 0; i < mid; i++) {
				leftArr[i] = arr[i];
			}

			// 중간을 기준으로 오른쪽 배열을 생성 (Create Right Array Based On Middle)
			for (int i = 0; i < len - mid; i++) {
				rightArr[i] = arr[i + mid];
			}

			// 나누어진 배열을 재귀호출 (Recurse Divided Array)
			mergeSort(leftArr);
			mergeSort(rightArr);

			// 정렬 및 합병 (Sort And Merge)
			merge(leftArr, rightArr, arr);
		}
	}

	private static void merge(int[] leftArr, int[] rightArr, int[] arr) {
		// 각 배열의 진행 인덱스 (Array's Current Index Variables)
		int leftIndex = 0;
		int rightIndex = 0;
		int arrIndex = 0;

		// 왼쪽 배열을 기준으로 루프 (Loop Based On Left Array)
		while (leftIndex < leftArr.length) {
			// 오른쪽 배열에서 채울 아이템이 있다면 (If Items Exist In Right Array)
			if (rightIndex < rightArr.length) {
				// 왼쪽 배열과 오른쪽 배열에서 각각 한개씩 꺼내와서 비교 후 결과 배열에 담음 (Pick Up One Of Left Item And One Of Right Item And Compare Which Is Smaller)
				if (leftArr[leftIndex] < rightArr[rightIndex]) {
					arr[arrIndex] = leftArr[leftIndex];
					leftIndex++;
				}

				else {
					arr[arrIndex] = rightArr[rightIndex];
					rightIndex++;
				}

				arrIndex++;
			}

			// 오른쪽 배열에서 채울 아이템이 없다면 (If There Isn't Item In Right Array)
			else {
				while (leftIndex < leftArr.length) {
					arr[arrIndex] = leftArr[leftIndex];
					leftIndex++;
					arrIndex++;
				}
			}
		}

		// 왼쪽 배열 처리 후, 오른쪽 배열에서 아이템이 남아있는 경우 그냥 채움 (After Left Array Processing, Fill Result Array With Right Items)
		while (rightIndex < rightArr.length) {
			arr[arrIndex] = rightArr[rightIndex];
			rightIndex++;
			arrIndex++;
		}
	}
}