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

배열을 정렬하는 Arrays.sort()와 컬렉션을 정렬하는 Collections.sort()는 각기 다른 알고리즘을 이용하여 정렬을 수행한다. 

정렬에 따라 시간 초과 문제가 발생할 수도 있어 다음 내용을 숙지하고 있도록 한다.

 

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort	평균, 최악 : O(nlog(n))

 

최악의 경우에도 O(nlog(n))의 시간복잡도를 갖고 있는 Collections.sort()를 표준 정렬 알고리즘으로 채택하고 있다고 한다.