Merge Sort 구현(Java)

💡 Merge Sort란?

합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

 

분류	정렬 알고리즘
자료구조	배열
최악 시간복잡도	O(n log n)
최선 시간복잡도	O(n log n)
평균 시간복잡도	일반적으로, O(n log n)
공간복잡도	О(n)

 

<참고>

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

합병 정렬 - 위키백과, 우리 모두의 백과사전

 

💡 Merge Sort - Java Code 구현

import java.util.*;

public class Merge_Sort {

    public static int[] src;
    public static int[] tmp;
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	
        int n = sc.nextInt();
        src = new int[n];
        
        for(int i=0; i<n; i++) {
        	src[i] = sc.nextInt();
        }
    	
        tmp = new int[src.length];
        
        merge(0, src.length-1);
        print(src);
        sc.close();
    }

    public static void merge(int left, int right) {
        if (left<right) {
            int mid = (left+right) / 2;
            merge(left, mid);
            merge(mid+1, right);

            int l = left;
            int r = mid + 1;
            int idx = l;

            while (l<=mid || r<=right) {
                if (r>right || (l<=mid && src[l]<src[r])) {
                    tmp[idx++] = src[l++];
                } else {
                    tmp[idx++] = src[r++];
                }
            }

            for (int i=left;i<=right;i++) {
                src[i]=tmp[i];
            }
        }
    }

    public static void print(int[] a) {
        for (int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println();
    }
}

 

📍 Test Case 출력 확인

Merge Sort Test case 확인하기