[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교

알고리즘을 풀다가 흔하디 흔한 sort() 정렬의 차이가 궁금해졌다.

 

보편적으로 배열을 정렬할 땐 Arrays.sort(), 컬렉션(List,Set..)을 정렬할 땐 Collections.sort()를 사용한다.

찾아보니 같은 sort 메서드지만 내부에서는 다른 정렬방식을 사용하여 정렬한다고 한다. 이에 따라 시간복잡도도 달라 각 자료구조를 사용할 때 효율성 테스트의 성공/실패 결과가 달라질 수 있다. 이에 대한 내용을 간단히 정리해보자.

 

---

 

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort (삽입정렬과 합병정렬을 결합한 정렬)	평균, 최악 : O(nlog(n))

 

따라서 최악이 O(nlog(n))의 시간복잡도를 갖고 있는 Collections의 sort()이 더 빠르며 평균 정렬 알고리즘으로 채택하여 사용하고 있다고 한다.
(특별한 제약이 없다면 무조건 Collections.sort()을 사용하기 보단 상황에 맞는 것을 사용하면 될 것 같다.)

 

 

참고

https://laugh4mile.tistory.com/175

[JAVA] 정렬에 대한 고찰 (Arrays.sort() 와 Collections.sort())