알고리즘 : 병합정렬(Java)

병합정렬

 

• 분할정복 알고리즘의 일종!
• 시간복잡도 : O(NlogN)
• 배열을 더이상 나눠지지 않을 때까지 반으로 나눈 후 각각을 정렬하여 병합하는 방식
• 별도의 배열을 생성하여 정렬한 요소들을 담아줘야 함
  => 정렬 과정에서 계속 정렬 상태가 유지되는 안정 정렬 방식

 

 

 

 

정렬 방식

 

1. 배열을 반으로 나눈다.  (분할)
   
   
2. 왼쪽 배열의 1번째 인덱스, 오른쪽 배열의 1번째 인덱스부터 비교 (정렬)
3. 작은 것을 우선으로 새로운 배열에 옮긴다. (병합)

 

 

병합정렬 과정

 

 

 

 

 

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            merge(array, left, mid, right);
        }
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int L = mid - left + 1;
        int R = right - mid;

        int[] leftArray = new int[L];
        int[] rightArray = new int[R];

        for (int i = 0; i < L; ++i) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < R; ++j) {
            rightArray[j] = array[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < L && j < R) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < L) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < R) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] data = {12, 11, 13, 5, 6, 7};
        mergeSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}