머지소트는 합병정렬이라고도 부르며 분할 정복 방법을 통해 구현한 정렬 알고리즘입니다.

빠른 정렬 알고리즘 중 하나로 분류되며, Quick Sort와 함께 가장 많이 언급되는 정렬방식 입니다.

퀵소트와는 반대로 안정정렬이라는 특성을 갖고있죠.

시간복잡도는 평균, 최선, 최악 모두 O(nlogn)입니다.

public static void callMergeSort(int[] arr){
    int [] tmp = new int[arr.length]; // 임시 저장소
    mergeSort(arr,tmp,0,arr.length-1);
  }
  public static void mergeSort(int[] arr, int[] tmp, int start, int end){
    if(start<end){
      int mid = (start+end)/2;
      mergeSort(arr, tmp, start, mid);
      mergeSort(arr, tmp, mid+1, end);
      merge(arr,tmp,start,mid,end);
    }
  }
  public static void merge(int[] arr, int[] tmp, int start, int mid, int end){
    for(int i = start; i<=end; i++){
      tmp[i]=arr[i];
    }
    int part1 = start; // 앞쪽 배열의 시작점
    int part2 = mid+1; // 뒤쪽 배열의 시작점
    int index = start; // 비교한 값을 할당할 인덱스
    while(part1<=mid && part2<=end){
      if(tmp[part1]<=tmp[part2]){
        arr[index]=tmp[part1];
        part1++;
      }else{
        arr[index]=tmp[part2];
        part2++;
      }
      index++;
    }
    //앞쪽에 남아있는 데이터를 추가해주자.
    for(int i = 0; i<=mid-part1; i++){
      arr[index+i]=tmp[part1+i];
    }
  }

원리

• 요소를 쪼갠 후 다시 합병시키며 정렬해나가는 방식으로 퀵정렬와 유사합니다.

1. 가운데 값을 기준으로 배열을 두개로 분리합니다.
2. 원소를 더이상 쪼갤 수 없을때, 왼쪽과 오른쪽 두부분 배열을 합치는 과정이 merge 함수에서 일어납니다.
3. merge함수는 앞쪽배열의 시작점과 뒤쪽배열의 시작점을 기준으로 두 배열을 합쳐나가며 arr을 갱신합니다.

장점

• 데이터 분포에 영향을 덜 받습니다. 입력데이터에 상관없이 정렬되는 시간은 O(N log N)으로 동일합니다.
• 크기가 큰 레코드를 정렬한 경우 LinkedList를 사용한다면 병합정렬은 퀵 정렬을 포함한 다른 어떤 정렬방법보다 효율적입니다.
• 안정정렬입니다.

단점

• 임시배열이 필요합니다. → 메모리 낭비
• 레코드의 크기가 큰 경우 이동횟수가 많이 발생하여 시간적으로 낭비가 발생한다고 합니다. 이 말은 이해가 잘안가네요 ..

참고