Java 프로그래밍에서 병합 정렬 알고리즘을 실현하는 실례 강좌

알고리즘 개요/사고방식
병합 정렬은'분치'(divide and conquer) 라고 불리는 정책을 기반으로 한다.그 기본적인 사고방식은 다음과 같다.
1. 두 개의 질서정연한 수조를 하나의 질서정연한 수조로 합치려면 다음과 같은 코드를 쉽게 쓸 수 있다.

//both a and b is ascend.
public void merge(int[] a, int[] b, int[] c){
  int i=0,j=0,k=0;
  while (i<=a.length && j<=b.length){
    if (a[i]<=b[i]){
      c[k++]=a[i++];
    }
    else{
      c[k++]=b[j++];
    }
  }
  while (i<=a.length){
    c[k++]=a[i++];
  }
  while (j<=b.length){
    c[k++]=b[j++];
  }
}

이러한 합병 알고리즘은 효율적이고 시간 복잡도가 O(n)에 이를 수 있음을 쉽게 알 수 있다.
2. 만약에 무질서한 수조가 정렬을 필요로 하지만 완전히 구분된 두 개의 서브수조 A와 B가 각각 정렬되어 있다면 상술한 코드를 빌려 우리도 쉽게 실현할 수 있다.
3. 그렇다면 A, B가 무질서하면 어떻게 하나요?그것들을 더 작은 수조로 나눌 수 있다.
4. 이렇게 최소로 나누면 모든 하위 그룹은 하나의 원소만 있고 질서수 그룹으로 볼 수 있다.
5. 이 가장 작은 수조부터 위의 절차를 거슬러 합치면 전체 수조가 배열된다.
요컨대 병합 정렬은 병합을 사용하는 것이다. 먼저 수조를 서브수조로 분해한 다음에 수조를 병합하는 것이다.
예제
다음은 예를 들어 만약에 수조 a={2,1,3,5,2,3}를 정렬하려면 수조를 {2,1,3}과 {5,2,3} 두 개의 서브수조로 나누면 이 두 서브수조가 정렬된 후에 {1,2,3}와 {2,3,5}로 변한 다음에 이 두 개의 서브수조를 통합하여 조작하면 최종 질서수조를 얻을 수 있다.코드는 다음과 같습니다.

void sort(int[] a) {
  int[] aux = new int[a.length];  // 
  mergeSort(a, 0, a.length - 1, aux);
}

void mergeSort(int[] a, int lo, int hi, int[] aux) {
  if (hi <= lo)
    return;
  int mid = lo + (hi - lo) / 2;
  mergeSort(a, lo, mid, aux);
  mergeSort(a, mid + 1, hi, aux);
  merge(a, lo, mid, hi, aux);

}

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    aux[k] = a[k];
  }
  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++];
    else if (j > hi)
      a[k] = aux[i++];
    else if (aux[i] <= aux[j])
      a[k] = aux[i++];
    else
      a[k] = aux[j++];

  }
}

또 다른 실현: 밑에서 위로 병합 정렬
위의 실현에서 하나의 큰 문제를 작은 문제로 나누어 각각 해결한 다음에 모든 작은 문제의 답안으로 전체 큰 문제를 해결하는 것과 같다.큰 그룹의 정렬을 작은 그룹의 정렬로 나누는 것은 위에서 아래로 정렬하는 것이다.또 하나의 실현은 밑에서 위로 올라가는 정렬이다. 즉, 먼저 두 개를 합친 다음에 네 개를 합친 것이다.코드는 다음과 같습니다.

void sort(int[] a) {
  int N = a.length;
  int[] aux = new int[N];
  for (int sz = 1; sz < N; sz += sz) {
    for (int lo = 0; lo < N - sz; lo += sz + sz) {
      // ， 
      merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
    }
  }
}