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

백준 2751번 문제를 풀어보다가 궁금해졌다.

처음 문제를 보고 단순히 배열에 담고 Arrays.sort를 이용해 풀었더니 시간초과가 났다.
그리고 ArrayList에 담아서 Collections.sort를 사용했더니 시간은 좀 걸렸지만 풀렸다! 뭐지? 하면서 두가지의 차이에 대해 찾아봤다.

Arrays.sort() : DualPivotQicksort

Arrays.sort()를 메서드를 클릭하면 다음과 같이 나온다.

듀얼 피벗 퀵 솔트는 평균 O(nlog(n))의 시간복잡도를 가진다고 하며 최악의 경우 O(n^2)의 시간복잡도를 가진다.

Collections.sort() : Timsort

Timsort란 삽입 정렬과 합병정렬을 결합하여 만든 정렬이라고한다. Timsort의 시간복잡도는 평균 O(n log(n)) 이며 최악의 경우도 O(n log(n)) 이다. 삽입정렬의 평균 시간 복잡도가 O(n^2) 인걸 감안하면 굉장히 효율이 좋은 정렬 방법이 아닐 수 없다.

참고자료 : https://d2.naver.com/helloworld/0315536

위 블로그에 가보면 정리를 엄청나게 잘 해놓으셨다.

정리하면 Collections.sort()를 사용하면 훨씬 빠르게 정렬할 수 있다.