Javascript Array.sort의 시간복잡도

알고리즘 문제를 풀다보면 javascript에서 지원하는 Array API 중 sort를 사용할 일이 굉장히 많다.
문제를 풀면서 항상 의문이 들었던 건 각 정렬 알고리즘 마다 데이터 조건에 따라 시간복잡도가 다르게 나오는데 javascript 엔진에서는 sort 함수를 어떻게 처리하는지 궁금하여 찾아보게 되었다.

정렬 알고리즘 중 특정 조건만 만족하면 가장 빠른 계수 정렬(counting sort)처럼 알고리즘마다 시간복잡도가 다르게 계산된다.

Firefox

Mozilla의 SpiderMonkey엔진에서는 sort 메서드의 내부 알고리즘으로 병합정렬(Merge sort)을 사용한다고 한다.
big o cheat sheet에서 확인해보면 병합 정렬의 시간 복잡도는 best, average, worst 모두 아래와 같은걸 확인할 수 있다.

O(n log n)

Chrome

Chrome의 V8 엔진은 병합정렬(Merge sort)과 삽입정렬(Insert sort)의 하이브리드 버전인 타임정렬(Time sort)을 내부 알고리즘으로 사용하고 있다고 한다.
big o cheat sheet에 따르면 타임정렬은 best의 시간복잡도가 더빠른 편이다.

best: O(n)
average: O(n log n)
worst: O(n log n)

Performance 비교

아래 내용은 Big O 표기법이 변동성까진 예측하지 못한다는 것을 보여준다.

아래 차트를 보면 파란색으로 표시된 데이터는 Array.sort를 통해 정렬된 시간이며, 총 500개의 랜덤 길이를 가진 배열을 대상으로 테스트 했다. 배열의 길이는 100 <= n <= 500000 사이이다. 시간 복잡도는 $O(nlogn)$ 정도 걸리는 것을 볼 수 있다.

주황색으로 표시된 데이터는 거의 정렬된 배열을 대상으로 Array.sort를 실행한 결과이다. $O(n)$ 정도의 시간이 걸리는 것을 볼 수 있다.

단순히 Big O 표기법으로만 봤을 때, 타임정렬(Time sort)이 더 빠를 것으로 예측하지만 위 차트를 보면 그렇지 않다. 타임정렬(Time sort)이 병합정렬(Merge sort)에 비해 더 넓은 변동성을 보여주는 것을 확인할 수 있다.

정리

파이어폭스와 크롬의 내부 정렬 알고리즘을 알아 보았다. stackoverflow의 답변 중 성능 측정과 관련된 내용도 흥미로워서 가져왔는데, Big O 표기법의 함정을 발견할 수 있었다. 데이터 조건에 따라서 적절한 정렬 알고리즘을 택하는 것이 중요할 것이다.

Reference

stackoverflow