7. Merge sort

1) Merge sort
merge sort는 전체 배열을 좌우 두 배열로 나누어 각각 자기사진 sort함수를 호출해 정렬하고, merge(병합)한다.
 
sort함수에서 sort함수를 호출하기 때문에, recursive하게 실행된다.
merge함수는 좌우가 정렬되어있다는 것을 확인한 후, 현재 배열을 복사하고, 그것을 이용하여 원래의 배열에 값을 집어넣으면서 정렬한다. 배열에 값을 집어넣은 merge방식은 다음과 같다.
1) 복사 배열의 좌우 배열의 맨 왼쪽에 각각 포인터를 두고, 원 배열의 맨 왼쪽에 포인터를 둔다.
2) 좌우배열의 포인터들의 값을 비교해 작은 값을 원 배열의 포인터에 집어넣는다
3) 원 배열의 포인터를 오른쪽으로 이동시키고, 값을 삽입한쪽 부분배열의 포인터를 오른쪽으로 이동시킨다.
4) 좌우배열의 포인터가 각각의 끝부분에 도달할때까지 반복한다.
 
ex)
1 3 4 6 | 2 5 7 9 
1 // 1 3 4 6 | 2 5 7 9
1 2 // 1 3 4 6 | 2 5 7 9
1 2 3 // 1 3 4 6 | 2 5 7 9
1 2 3 4 // 1 3 4 6 | 2 5 7 9 
1 2 3 4 5 // 1 3 4 6 | 2 5 7 9 
1 2 3 4 5 6 // 1 3 4 6 | 2 5 7 9 
1 2 3 4 5 6 7 // 1 3 4 6 | 2 5 7 9 
1 2 3 4 5 6 7 9 // 1 3 4 6 | 2 5 7 9 
 
좌우배열의 비교하여 원 배열로 옮기는 횟수만큼 비교하므로 merge의 실행시간은  ~N이 된다.
따라서 수학적으로, 길이가 N인 배열의 정렬 실행시간를 T(N)이라고 하고, N을 power of 2라고 했을 때,
T(N) = 2T(N/2) + N (N > 1, T(1)=0)
T(N)/N = 2T(N/2)/N + 1
            = 2(2T(N/4) + N/2)/N + 1
            = 4T(N/4)/N + 1 + 1
            = 4(2T(N/8) + N/4)/N + 1 + 1
            = 8T(N/8)/N + 1 + 1 + 1
            ....
            = NT(N/N)/N + 1 + 1+ 1 +... +1
            = logN
T(N) = NlogN 의 실행시간을 갖게 된다.
하지만, 배열의 복사를 위해서 추가적인 공간을 사용한다는 단점이 있다.
또한, mergesort는 부분배열로 계속 나누고, 배열의 크기가 특정 수준으로 작아질 경우(예를 들어 7이하) Insertion sort 등으로 처리하는 것이 overhead를 줄이는 방법이다.
또한, 좌측배열의 가장 오른쪽과 우측배열의 가장 왼쪽을 비교해, 우측배열의 가장 왼쪽이 더 크거나 같을 경우 미리 정렬 된것으로 보고 merge 안하고 끝내버리는 방식으로 성능을 향상 시킬 수 있다.
 
2) Bottom-up mergesort
bottom-up mergesort는 기본적으로 merge함수의 동작방식은 동일하지만, 전체를 두 부분으로 나누는 것으로부터 시작하는 recursive방식이 아닌, 처음부터 가장 작은 단위의 size로 부분배열을 여러개로 나누어 각각 정렬 하고, merge를 반복문을 이용해 시도한다. 하지만, recursive방식보다 10%정도 느리고 동일하게 복사배열을 사용한다.
 
3) Sorting Complexity
Mergesort는 정렬의 계산모델은 decision tree이다.
decision tree의 끝에 있는 leaves는 정렬 결과를 나타낸다.
정렬 결과의 총 경우의 수는 가능한 순열의 총 갯수이므로, 길이가 N인 배열에 대해 N! 이다.
decision tree의 높이가 h일 때, 최대 leaves는 완전이진트리의 leaves갯수인 2^h이다.
따라서, 길이가 N인 배열에 대해 decision tree 높이가 h라면 다음을 만족한다.
2^h >= N!
h >= log(N!) 
그런데, log(N!) ~NlogN이라는 것이 증명되어 있으므로
h >= NlogN 이고, 알고리즘의 lower bound가 NlogN이 된다.
그런데 우리가 이전에 merge sort가 NlogN성능임을 확인했으므로,  upper bound는 NlogN이 되고,
Sorting에서 Optimal algorithm은 NlogN이 된다.
따라서, 우리는 더 나은 성능을 가진 알고리즘을 찾을 필요가 없다.
 
하지만, 우리가 Input에 대해 특정한 정보를 가지고있을 경우, 최적의 알고리즘의 성능이 NlogN이라고 보장할 수 없고, 더 나은 성능의 알고리즘을 개발할 수 있다.
 
4) Comparator, Stability
 
여러 변수들을 가지는 클래스를 구현할 경우, 내부에 comparator interface로 클래스를 구현할 수 있다. 객체끼리 비교를 할 때 어떤 변수를 기준으로 비교할 것인지 정해주는 parameter를 추가로 받아서,  sort시에 해당 변수에 대해서 객체를 정렬하도록 할 수 있다.
예를 들어, Student class에 name, grade 변수가 존재한다면,
Arrays.sort(arr1, Student.BY_Name) 과 같이 하면 이름을 기준으로 정렬된다.
이후에 Arrays.sort(arr1, Student.BY_Grade) 를 이용하면, 추가로 점수를 기준으로 정렬된다.
그런데 생각해보자. 여러 이름이 동일한 점수를 가지고, 점수를 기준으로 정렬 할 때,
동일 점수에 대한 이름의 상대적순서가 정렬 전과 동일하게 유지된다면 동일한 점수에 대해서 깔끔하게 이름순으로 정렬되어 우리가 원하는 결과일 것이다. 하지만, 그렇지 않다면 점수로 정렬할 때, 이름의 순서는 다시 뒤죽박죽하게 섞여서 이전에 이름순으로 정렬한 결과는 다시 엉망이 되어버릴 것이다.
따라서, 여러 변수를 가지는 데이터에서 하나의 변수에 대해서 정렬을 시도할 때, 해당 변수의 동일한 값에 대해서 다른 변수들의 상대적 순서가 이전과 같이 유지되어야 stable한 sort라고 할 수 있다.
이러한 stable한 sort는 Insertion sort, merge sort가 있고,
unstable한 sort는 selection sort, shell sort, quick sort가 있다.
 
예를 들어, 아래는 목적지에 따라 정렬된 표이다.

목적지	출발시간
서울	9:00
서울	10:00
시리아	10:00
시리아	9:00

 
Selection sort로 출발시간을 정렬할 경우, 아래와 같이 되어 서울이 시리아 밑에 있어 stability가 깨진다.

목적지	출발시간
서울	9:00
시리아	9:00
시리아	10:00
서울	10:00

 
Insertion sort로 출발시간을 정렬할 경우, 아래와 같이 되어 목적지의 상대적 위치가 유지된다(stable)

목적지	출발시간
서울	9:00
시리아	9:00
서울	10:00
시리아	10:00