[Java] Arrays.sort(), Collections.sort()

알고리즘 문제를 풀면서 sort() 메서드를 사용할 때, 정렬 방식과 시간 복잡도 차이가 있다는 것을 알게 되었다.

그래서 오늘은 Java에서 제공하는 sort() 메서드에 대해 정리해 보려고 한다.

 

📌 Java의 주요 정렬 메서드

자바에서 정렬을 수행할 때 주로 사용하는 정렬 메서드는 다음과 같다.

• Arrays.sort() → 배열 정렬
• Collections.sort() → 리스트 정렬

두 메서드는 내부적으로 다른 정렬 알고리즘을 사용하므로, 시간 복잡도와 안정성(Stable Sort 여부)이 다를 수 있다.

 

📌 정렬 방식과 시간 복잡도 비교

정렬 메서드	정렬 알고리즘	평균 시간 복잡도	최악 시간 복잡도	안정 정렬 여부
Arrays.sort()    (기본 타입)	Dual-Pivot QuickSort	O(n log n)	O(n²) (최악)	❌ (비안정 정렬)
Arrays.sort()    (객체 배열)	TimSort    (Merge + Insertion)	O(n log n)	O(n log n)	⭕ (안정 정렬)
Collections.sort()	TimSort    (Merge + Insertion)	O(n log n)	O(n log n)	⭕  (안정 정렬)

💡 안정 정렬(Stable Sort)이란 ?

동일한 값을 가진 요소가 정렬 후에도 기존 상대적 순서를 유지하는 정렬 방식을 말한다.

 

📌 각 정렬 방식의 특징

1️⃣ Arrays.sort()

• 기본 타입 배열 (int[], double[] 등) → Dual-Pivot QuickSort 사용
• 객체 배열(Integer[], String[] 등) → TimSort 사용
• 기본 타입 배열 정렬 시 비안정 정렬(unstable sort)
• 객체 배열 정렬 시 안정 정렬 (stable sort)

int[] arr = {5, 2, 9, 1, 5};
Arrays.sort(arr); // Dual-Pivot QuickSort 사용

2️⃣ Collections.sort()

• 내부적으로 List.sort()를 호출 → TimSort (합병 정렬 + 삽입 정렬) 사용
• List<T>에서 Comparable을 구현한 요소 정렬 가능
• 안정 정렬 (stable sort) 보장

List<Integer> list = Arrays.asList(5, 2, 9, 1, 5);
Collections.sort(list); // TimSort 사용

 

---

 

sort() 메서드의 차이를 확인해 보기 위해 백준 2751 수 정렬하기 2 문제를 예시로 들어보자.

 

처음에는 Arrays.sort()를 사용하여 정렬을 시도했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();
        for (int num : arr) {
            sb.append(num).append("\n");
        }

        System.out.println(sb.toString());

        br.close();
    }
}

이 방식은 Dual-Pivot QuickSort를 사용하여 평균 O(n log n)이지만, 최악의 경우 O(n²)로 인해 시간 초과가 발생할 수 있다.

 

이 문제를 Collections.sort()를 사용하여 해결하면 시간 초과를 피할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);

        StringBuilder sb = new StringBuilder();
        for (int num : list) {
            sb.append(num).append("\n");
        }

        System.out.println(sb.toString());

        br.close();
    }
}

Collections.sort(List<Integer>)는 TimSort를 사용하여 최악의 경우에도 O(n log n)을 보장하므로 훨씬 안정적인 정렬 성능을 제공한다.