Merge Sort (합병 정렬)

	public class MergeSort {
	public static void main(String[] args) {
	int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
	mergeSort(intArray, 0, intArray.length);
	for (int i = 0; i < intArray.length; i++) {
	System.out.print(intArray[i] + " ");
	}
	System.out.println("");
	}
	// { 20, 35, -15, 7, 55, 1, -22 }
	public static void mergeSort(int[] input, int start, int end) {
	// length가 1이면 mergeSort에서 아무 것도 하지 않는다.
	// end는 array의 실제 마지막 index보다 1이 크다.
	if (end - start == 1) {
	return;
	}
	int mid = (start + end) / 2; // mid: right side의 첫번째 index
	// length가 1일 경우, 하단 mergeSort 2개는 스킵(아무것도 하지 않음)
	mergeSort(input, start, mid); // left side
	mergeSort(input, mid, end); // right side
	merge(input, start, mid, end);
	}
	// { 20, 35, -15, 7, 55, 1, -22 }
	public static void merge(int[] input, int start, int mid, int end) {
	// Optimization
	// right side의 첫번째 요소가 left side의 마지막 요소보다 크거나 같으면, 순서 그대로 유지.
	if (input[mid - 1] <= input[mid]) {
	return;
	}
	// (정렬하면서) merge 시작
	int i = start;
	int j = mid;
	int tempIndex = 0;
	// temp: 정렬된 값들을 넣어 놓을 임시 array
	int[] temp = new int[end - start];
	// left, right side 각각 범위 내에 있는 동안, temp로 복사
	while (i < mid && j < end) {
	temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
	}
	// right side 먼저 끝나면, 남아 있는 left side의 요소들은 정렬된 후 가장 뒤쪽에 있을 것이 확실함
	// 따라서 input의 맨 뒷 부분으로 이동시켜 놓는다.
	// mid - i: left side에서 아직 temp로 이동되지 않은 요소의 개수.
	// 0이면 아무 것도 하지 않음(left side 먼저 끝났을 경우)
	System.arraycopy(input, i, input, start + tempIndex, mid - i);
	// 정렬된 temp를 tempIndex만큼 다시 input으로 copy (merge 끝)
	System.arraycopy(temp, 0, input, start, tempIndex);
	}
	}

view raw MergeSort.java hosted with ❤ by GitHub

• merge할 때 추가적인 배열이 필요하므로, 제자리 정렬(in-place)이 아니다.

• 시간 복잡도는 O(NlogN)이다. 절반씩 split하므로 logN에 요소의 개수만큼 비교하고 합병하므로 N을 곱한다.

• 안정적이다(stable). 왼쪽 절반과 오른쪽 절반의 인덱스 i와 j 위치에 있는 요소를 비교하여, 같으면 위치를 바꾸지 않고 순서를 그대로 유지한다.