mergeSort

mergeSort.java

/**
* 비순환 드라이버 method
* @param arr
*/
void mergeSort(int[] arr) {
  mergeSort(arr,0,arr.length);
}

/**
* 합병 정렬 - 분할하는 로직이 들어있고, 다른 합병정렬 알고리즘을 가지고 있는 함수를 실행합니다.
* @param arr 배열
* @param startIndex 시작 index
* @param last 처음에 배열의 길이를 입력 받고, -1 해서 마지막 인덱스로 사용됩니다. 
*/
void mergeSort(int[] arr, int startIndex, int last) { // 오버로드로 선언 매개변수 개수만 다릅니다.
  // 선조건 : 0 < startIndex < last <= arr.length
  // 후조건 : arr[startIndex...last-1]은 오름차순이다.
  if(last - startIndex < 2) return;
  int middleIdex = (last + startIndex) / 2; // 배열의 중간 index

  mergeSort(arr, startIndex, middleIdex); // [startIndex, middleIdex) 반열린구간 
  mergeSort(arr, middleIdex, last); // [middleIdex, last) 반열린구간 
  merge(arr, startIndex, middleIdex, last);
}

/**
* 합병하는 알고리즘입니다.
* @param arr
* @param startIndex
* @param middleIdex
* @param last
*/
void merge(int[] arr, int startIndex, int middleIdex, int last) {
  // 선조건 : arr[startIndex...middleIdex-1] 과 arr[middleIdex...last-1] 은 오름차순이다.
  // 후조건 : arr[startIndex...last-1] 은 오름차순이다.
  if(arr[middleIdex -1] <= arr[middleIdex]) return;
  int i = startIndex, j = middleIdex, k = 0; // k는 합병된 원소의 개수입니다.
  int[] tempArr = new int[last - startIndex]; // 합병할때만 사용하는 임시 배열
  while (i < middleIdex && j < last) // main loop
    if(arr[i] < arr[j]) tempArr[k++] = arr[i++]; 
    else tempArr[k++] = arr[j++]; 
  if(i < middleIdex) System.arraycopy(arr, i, arr, startIndex + k, middleIdex - i); 
  // shift arr[i...midddleIndex - 1] 
  System.arraycopy(tempArr, 0, arr, startIndex, k); // copy tempArray[0...k-1] to arr[p...p+k-1]
}