(자료구조)merge sort 예제

public class mergeTest {
    public static int[] src;
    public static int[] tmp;
    
    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;    //start는 항상 mid+1보다 작기 때문에, 분할의 저장 위치는 start 지점이 된다. 그래서 int idx는 p가 된다.
 
            while (p<=mid || q<=end) {    //p가 mid이하거나 q가 end이하일 때 동작해야 한다. 미만이 아닌 이유는 원소의 개수가 1개일 때까지 쪼개기 때문이다.
 
                if (q>end || (p<=mid && src[p]<src[q])) {    //두 번째 분할의 원소를 이미 다 가져온 경우 (q> end), 첫 번째 분할에서 가져오지 않은 원소가 있고, 첫번째 분할의 첫 원소 값이 두 번째 분할의 첫 원소 값보다 작은 경우(p<=mid && src[p]<src[q])
                    tmp[idx++] = src[p++]; 
                }else {
                    tmp[idx++] = src[q++];
                }
            }
            
            for (int i=start;i<=end;i++) {
                src[i]=tmp[i];
            }
        }
    }
 
    public static void main(String[] args) {
        src = new int[]{1, 9, 8, 5, 4, 2, 3, 7, 6};
        tmp = new int[src.length];
        mergeSort(0, src.length-1);
        System.out.print(Arrays.toString(src));
    }
 
}