합병 정렬 ( merge sort )

주제(Subject)
--------------------------------------------------------
한글(약어) : 합병 정렬()
영어(약어) : merge sort()


관련개념(Related Concepts)
--------------------------------------------------------
정렬
알고리즘
비교기반 정렬


개요(Summary)
--------------------------------------------------------
분할정복 방법에 따라, 자료를 부분배열로 나눈 후, 오름/내림차순으로 정렬하는 방법.
퀵정렬의 단점을 보완한다.
안정적
제자리정렬 가능함


본문(Body)
--------------------------------------------------------
1. 합병정렬의 성질

In computer science, merge sort or mergesort is an O(n log n) sorting algorithm. It is easy to implement merge sort such that it is stable, meaning it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It is a comparison sort. The algorithm was invented by John von Neumann in 1945.
                                                                      - from Wikipedia : Merge Sort

2. 소스코드
   1) Java (from Wanginator)

public class MergeSort {
    public static void mergesort (int[] a) {
        mergesort(a, 0, a.length-1);
    }

    private static void mergesort (int[] a, int l, int r) {
        //base case: a[l..r] is empty or has only one element
        if ( l>=r ) return;

        //recursion step: a[l..r] is not empty
        //divide into sublists and merge
        int m = (l+r)/2;
        mergesort (a, l, m);
        mergesort (a, m+1, r);
        merge (a, l, m, r);
    }

    //merges to sublists
    private static void merge (int[] a, int l, int m, int r) {
        //base case: second sublist is empty
        if (m+1>r) return;

        int[] b = new int[a.length]; //create temporary array
        //copy a[l..m] to b[l..m]
        for (int i=l; i!=m+1; i++) {
            b[i] = a[i];
        }
        //copy a[m+1..r] to b[m+1..r] in reverse order
        for (int i=m+1; i!=r+1; i++) {
            b[i] = a[r+m+1-i];
        }
        //merge b[l..m] with b[m+1..r] to a[l..r]
        int k=l; int j=r; //pointer wandering from outside inward
        for (int i=l; i!=r+1; i++) {
            if (b[k] <= b[j]) a[i] = b[k++];
            else a[i] = b[j--];
        }
    }
}

3. 시뮬레이션
   1) Gif Animation

Description Sorting a random list using merge sort Source Self-made using Matlab Date 2006-11-28 ,Author v1: Nuno Nogueira (Nmnogueira), v2: edited by Daniel Miller (cobaltBlue)

   2) Wanginator : Merge Sort - JavaApplet
      http://www.wanginator.de/studium/applets/mergesort_en.html

   3) The Animator :
      http://www.cs.hope.edu/alganim/animator/Animator.html



모임,단체(Commutities)
--------------------------------------------------------
1. Hope College Department of Computer Science| 27 Graves Place | Holland, MI 49423
   http://www.hope.edu/cs/


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Merge Sort
   http://en.wikipedia.org/wiki/Merge_sort

2. Wanginator : Merge Sort
   http://www.wanginator.de/studium/applets/mergesort_en.html

3. The Complete Collection of Algorithm Animations (CCAA) (Hope College Department of Computer Science| 27 Graves Place | Holland, MI 49423)
   http://www.cs.hope.edu/alganim/ccaa/index.html

4. Google Search : type [[merge sort site:*.edu]]@google
   http://www.google.com/search?source=ig&hl=en&q=merge+sort+site%3A*.edu