Arrays.sort()와 Collections.sort() 비교

코딩테스트 문제를 풀면서 문득

Arrays.sort()의 시간복잡도가 궁금해졌다

구글링 해보니 

 

Arrays.sort()는 듀얼 피벗 퀵소트 알고리즘을 사용하여 

평균 O(nlog(n))의 시간복잡도와 최악은 O(n^2)의 시간복잡도가 나온다고한다

 

 

Collectios.sort()의 경우, 합병정렬과 삽입정렬을 결합한 TimSort 알고리즘을 사용하여

최선 O(n) 시간복잡도, 평균 O(nlog(n))의 시간복잡도와 최악도 O(nlog(n))의 시간복잡도를 갖고있다고 한다.

 

 

 

따라서 정렬시 특별한 사유가 없으면 Collections.sort()를 사용하면 될 것 같다 

 

 

 

출처

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

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