Sorting에 대한 짧은 정리(NlogN, Merge정렬)

5. Merge Sorting

Merge정렬도 기본적으로 Divide and Conquor 방법으며 Recursive한  함수 호출 방식으로 구현한다. 아래와 같이 동작하며 수행 시간은 O(NlogN)이다

 

 

자바로 구현된 소스는 다음과 같다.

    public static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

       // base case
       if (hi - lo <= 1) return;

       // sort each half, recursively
       int mid = lo + (hi - lo) / 2;
       sort(a, aux, lo, mid);
       sort(a, aux, mid, hi);

       // merge back together
       merge(a, aux, lo, mid, hi);
    }
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
       int i = lo, j = mid;
       for (int k = lo; k < hi; k++) {
          if      (i == mid)                 aux[k] = a[j++];
          else if (j == hi) aux[k] = a[i++];
          else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];
          else                               aux[k] = a[i++];
       }

       // copy back
       for (int k = lo; k < hi; k++)
          a[k] = aux[k];
    }
    public static void sort(Comparable[] a) {
        int N = a.length;
        Comparable[] aux = new Comparable[N];
        sort(a, aux, 0, N);
    }

 

Divide and Conquor 방법 및 Recursion을 이용하여 코드도 깔끔하다