[JS] 자바스크립트 sort 알고리즘 - Tim Sort

얼마 전 퀵 정렬 알고리즘을 공부하면서 간단하게 퀵 정렬 알고리즘을 구현해보았다.

[정렬] 퀵 정렬 (tistory.com)

[정렬] 퀵 정렬

구현 후 테스트 겸 자바스크립트에서 제공하는 sort 메서드와 비교를 위해 랜덤한 배열을 만들고 시간을 비교해보았는데…

 

길이가 1,000인 배열을 정렬

길이가 10,000인 배열을 정렬

길이가 100,000인 배열을 정렬

 

위 결과와 같이 배열의 길이가 늘어날수록 sort 메서드가 정렬을 처리하는 속도가 빨랐다. 

(물론 내가 구현한 퀵소트가 부족한 부분이 있어서 더 차이가 많이 난것 같다)

이에 자바스크립트 sort 가 어떠한 알고리즘을 사용하는지 궁금해 조사해보았다.

sort()

자바스크립트 명세에는 sort 구현에 어떤 알고리즘을 사용해야 한다고 특정하지 않는다.

이 말은 자바스크립트를 해석하는 엔진을 어떻게 구현했냐에 따라 정렬에 사용되는 알고리즘에 달라질 수 있다는 것이다.

가장 많이 쓰이는 V8 엔진에서는 어떻게 구현했는지 찾아보자.

V8 깃허브에 가서 'sort'를 검색해보면 , third_party/v8/builtins/array-sort.tq라는 파일을 찾을 수 있다.

이 파일의 상단에 주석을 보면 아래와 같은 내용이 적혀져있다.

// This file implements a stable, adapative merge sort variant called TimSort.
"이 파일은 TimSort라는 안정적인 적응형 병합 정렬 변형을 구현합니다.".

V8은 정렬 알고리즘으로 Tim Sort 를 사용한다는 것을 알 수 있다.

Tim Sort 란?

2002년 소프트웨어 엔지니어 Tim Peters에 의하여 Tim sort 개발된 알고리즘으로 이 정렬 알고리즘은 **'Insertion Sort'**과 **'Merge Sort'**를 결합하여 만든 정렬이라고 한다.

실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn)이다. 최악의 시간 복잡도가 O(nlogn) 이기 때문에 많은 언어에서 표준 알고리즘으로 채택하여 사용한다고 한다.

 

참고

Tim sort에 대해 알아보자 (naver.com)

자바스크립트(JS)의 sort는 어떤 알고리즘을 사용할까? (velog.io)