[java] 자바의 합병 정렬(Merge Sort) 자료구조에 대해 알아보기

14 Dec 2023

java

합병 정렬은 재귀적으로 분할-정복 기법을 사용하여 리스트를 정렬하는 효율적인 알고리즘 중 하나입니다. 이 알고리즘은 안정적이며 비교 기반의 정렬 알고리즘 중 하나로 평균 시간복잡도가 O(nlogn)입니다.

합병 정렬의 작동 방식

합병 정렬은 아래의 단계로 작동합니다:

분할: 리스트를 반으로 나눕니다.
정복: 각각의 반쪽 리스트를 재귀적으로 합병 정렬을 적용합니다.
합병: 정렬된 반쪽 리스트를 합병하여 최종적으로 정렬된 리스트를 만듭니다.

자바에서의 합병 정렬 구현 예시

다음은 자바에서 합병 정렬을 구현한 예시입니다.

public class MergeSort {
    public static void merge(int[] arr, int left, int mid, int right) {
        // 머지 로직 구현
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

마치며

합병 정렬은 자바에서 정렬 알고리즘을 구현할 때 많이 활용되는 알고리즘 중 하나입니다. 이 알고리즘을 사용하면 효율적으로 리스트를 정렬할 수 있습니다.

더 많은 정렬 알고리즘 및 자료구조에 대해 알아보려면 GeeksforGeeks의 자료를 참고하실 수 있습니다.