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

1. Merge Sort(합병정렬)

👩‍💻 구현

package Algorithm;

public class merge_sort {
	private static int[] input = {5, 6, 2, 8, 7, 23, 4, 1};
	static int[] tmp = new int[input.length];

	public static void main(String[] args) {
		
		mergeSort(0, input.length-1);
		
		for(int i : input) {
			System.out.print(i + " ");
		}

	}
	
	public static void mergeSort(int start, int end) {
		if(start < end) {
			int mid = (start + end) / 2;
			//배열을 분할한다
			mergeSort(start, mid);
			mergeSort(mid+1, end);
			
			//두 분할의 첫번째 인덱스를 저장
			int p = start;
			int q = mid + 1;
			int idx = p;
			//오른쪽 배열을 끝까지 돌았거나, 왼쪽 배열을 다 돌기 전이고 왼쪽배열 값이 오른쪽배열 값보다 작을 때,
			//임시 배열에 왼쪽 배열 값을 저장
			while(p <= mid || q <= end) {
				if(q > end || (p <= mid && input[p] <= input[q])) {
					tmp[idx++] = input[p++];
				}else {//반대의 경우 임시 배열에 오른쪽 배열 값을 저장
					tmp[idx++] = input[q++];
				}
			}
			
			for(int i=start; i<=end; i++) {
				input[i] = tmp[i];
			}
			
		}
		
	}

}

https://ict-nroo.tistory.com/53?category=698685