Merge가 어떻게 이루어지는지 그림으로 보자.
[3,10,23,54,1,5,25,75] 다음과 같은 배열이 있다.
배열을 반으로 나눈다.
반으로 나눈 배열을 저장할 임시 배열 A를 만든다.
B와C를 비교해서 더 작은 수인 1을 A에 채운후 C의 인덱스는 1증가시킨다.
B를 x C를 y A를 result로 바꿔 주었다.(큰 의미는 없음)
이런식으로 계속 채워주면 된다.
mergesort는 이걸 배열 하나까지 모두 쪼개준다. 무슨 이야기냐 하면,
위의 그림처럼 하나까지 모두 쪼개준뒤, 정렬해서 다시 합쳐준다.
time complexity는 언제나 n개의 데이터를 가지고 log n 단계를 거치기 때문에 O(nlogn)이다.
recursive하게 진행되는 순서이다.
구현은 다음과 같다.
import java.util.*;
class Main {
public static void main(String[] args) {
int[] arr= {3,2,1,4,7,6,5,8,10,9};
MS.merge_sort(arr);
System.out.println(Arrays.toString(arr));
}
}
class MS{
static int[] tmp; // merge한 값들을 넣을 임시 배열
public static void merge_sort(int A[]){
tmp = new int[A.length];
mergeSort(A,0,9);
}
static void merge(int A[],int start,int mid,int end){
int i = start; //part1의 start
int j = mid+1; //part2의 start
int k = start; //tmp의 start
//두 배열 비교해서 더 작은값부터 하나씩 순서대로 넣기
while(i <= mid && j <= end){
if(A[i]<A[j]){
tmp[k] = A[i];
i++;
}else{
tmp[k] = A[j];
j++;
}
k++;
}
//part2가 먼저 다 채워졌다면
if(j > end){
while(i <= mid){
tmp[k] = A[i];
k++;
i++;
}
}
else{ // part1이 먼저 채워졌다면
while(j <=end){
tmp[k] = A[j];
k++;
j++;
}
}
//merge한 값 A에 복사
for(int l = start; l <= end;l++){
A[l] = tmp[l];
}
} // merge
static void mergeSort(int[] A,int start,int end){
// 쪼개다가 부분리스트가 1개만 있는경우 리턴
if(start == end) return;
int mid = (start+end)/2;
mergeSort(A,start,mid); // (왼쪽 start~mid)
mergeSort(A,mid+1,end); // 오른쪽 mid+1 ~ end
merge(A,start,mid,end);
}
}
구현하다가 계속 막힌 부분이 있었다. merge 함수에서 마지막 부분에 merge한 값을 원래 정렬하려고 했던 배열에 복사를 해주어야 한다.
그렇게 하지 않으면, merge로 생성된 상위 배열을 또 merge할때 merge했던 값이 저장되어 있지 않아, 아무것도 안한게 된다