Arrays.sort()와 Collections.sort()의 차이점

겔로그·2023년 10월 9일

Baeldung 글 중 Difference Between Arrays.sort() and Collections.sort()를 읽고 신기해 직접 코드를 확인해 봤고 이를 공유하고자 합니다.

Arrays.sort()

    public static void sort(long[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

Collections.sort()

    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

두 가지 로직을 확인한 결과 둘 다 Arrays.sort()를 호출하는 모습을 볼 수 있습니다. 하지만, Arrays.sort()에서는 primitive type과 reference type에서 정렬하는 방식이 달랐습니다.

Collections.sort()에서 호출한 Arrays.sort()

    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

primitive type의 경우, 정렬 방식을 Dual-pivot Quicksort를 사용하는 반면, reference type에 있어서는 Mergesort 혹은 Timsort를 활용중인 사실을 알 수 있습니다.

차이점

일반적으로 알려진 정렬방식의 시간복잡도 및 공간복잡도는 다음과 같습니다.

Dual-pivot Quicksort와 Mergesort의 차이점

Mergesort 같은 경우, stable sorting (동일한 값을 가진 원소들 사이의 순서가 정렬 이전과 정렬 이후에도 동일하게 유지)이 되는 반면, Quicksort의 경우 stable하지 못하다는 특징이 존재합니다.
Mergesort의 경우 시간 복잡도는 O(n log n), 공간 복잡도는 O(n) + O(logn) = O(n) 을 유지합니다. Quicksork의 경우 평균 시간 복잡도가 𝑂(nlogn)이나 최악의 경우 O(n^2) 의 시간이 걸립니다. 공간 복잡도는 O(logn)이어서 Mergesort보다 더 좋은 성능을 보여주고 있습니다.

최악을 고려할 경우 Mergesort를 사용하는 것이 Quicksort를 사용하는 것보다 안전하겠다는 생각이 들지만 왜 Arrays.sort에서는 Quicksort를 사용할까요?

사실 일반적인 케이스에서는 Quicksort가 Mergesort보다 빠르기 때문입니다.

quicksort가 mergesort보다 일반적으로 빠른 이유

Divide and conquer strategy: Quicksort uses a divide and conquer strategy to sort the array. It selects a pivot element and divides the array into two subarrays, one containing elements smaller than the pivot, and the other containing elements larger than the pivot. It then recursively sorts the two subarrays. This approach reduces the number of comparisons required to sort the array.

Randomized pivot selection: Quicksort selects the pivot element randomly, which reduces the likelihood of worst-case scenarios. The worst-case scenario occurs when the pivot is either the smallest or largest element in the array, which leads to unbalanced partitions and slows down the algorithm. Randomized pivot selection ensures that the probability of encountering a worst-case scenario is low.

Efficient use of memory: Quicksort is an in-place sorting algorithm, meaning that it doesn't require any additional memory to sort the array, except for the stack space needed for recursive calls. Other sorting algorithms like merge sort require additional memory to merge subarrays.

Cache efficiency: Quicksort is cache-efficient because it accesses contiguous memory locations, which can be efficiently cached. This reduces the number of cache misses, resulting in faster execution times.

Timsort란?

Timsort는 Mergesort와 Insertion sort 방식을 혼합한 정렬 알고리즘입니다.

Insertion sort가 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족하고 있어 표본이 작은 n에 있어서는 정렬 방식 중 성능이 가장 좋다는 특징이 있습니다.

이러한 특징을 이용하여 전체를 작은 덩어리로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어입니다.

Timsort에 대해서 좀 더 알아보고 싶으신 분들께서는 아래 글을 참고하시길 바랍니다.

참고: Tim sort에 대해 알아보자

왜 정렬 방식이 다를까?

Why does Java's Arrays.sort method use two different sorting algorithms for different types?
글을 참고할 경우 다음과 같은 해답을 얻을 수 있습니다.

일반적으로는 quicksort가 빠르다는 특징 때문에 안정성을 굳이 보장하지 않아도 되는 primitive type에 대해서는 Dual-pivot Quicksort를 사용합니다.

하지만, reference type의 경우에는 안정성이 보장되어야 하기에 stable sort를 활용한 것으로 판단됩니다.

결론(TL;DR)

Arrays.sort()와 Collections.sort()의 차이점은 Arrays.sort()가 인자별로 다른 정렬 방식을 사용하는데 있습니다.
primitive type에는 Dual-pivot Quicksort를 사용하며 reference type에 있어서는 Mergesort 혹은 Timsort를 사용합니다.
타입에 따른 정렬방식이 다른 이유는 안정성 보장 유무입니다. quicksort는 stable sort가 아니기에 정렬간 안정성을 보장하지 못합니다.