JavaScript로 배열을 정렬할 때 자주 사용하는 Array.prototype.sort() 메서드. 그런데 이 함수가 내부적으로 어떤 정렬 알고리즘을 사용하는지 궁금해진 적이 있으신가요? 결론부터 말하자면, ECMAScript 명세는 특정 정렬 알고리즘을 규정하지 않습니다. 구현 방식은 각 JavaScript 엔진 개발자의 선택에 맡겨져 있으며, 그 결과 서로 다른 엔진은 서로 다른 알고리즘을 사용합니다.
엔진별 정렬 알고리즘 차이
Mozilla (SpiderMonkey)
Firefox에 탑재된 SpiderMonkey 엔진은 병합 정렬(Merge Sort)을 사용합니다. 실제 구현 코드는 Mozilla 저장소에서 C 언어로 작성된 형태로 확인할 수 있습니다.
WebKit / Blink (Chrome, Safari 등)
Chrome과 Safari 등에서 사용되는 WebKit 계열 엔진은 하나의 알고리즘만 고정적으로 사용하지 않습니다. 대신 배열 요소의 데이터 타입과 배열 길이에 따라 최적의 알고리즘을 동적으로 선택합니다.
- 숫자형 배열: C++ 표준 라이브러리(std)의 퀵 정렬(Quick Sort) 함수를 활용합니다.
- 비숫자형 배열: 병합 정렬(Merge Sort)을 사용합니다.
- 기타 경우: 조건에 따라 선택 정렬(Selection Sort)도 사용됩니다.
정리
즉, sort() 함수의 내부 동작은 배열 요소의 데이터 타입과 배열 크기에 따라 달라질 수 있습니다. 따라서 성능이 중요한 대규모 데이터 처리 시에는 실행 환경(브라우저 및 엔진)별로 정렬 성능이 다를 수 있다는 점을 고려하는 것이 좋습니다. 참고로 ECMAScript 2019(ES10)부터는 sort()가 반드시 안정 정렬(stable sort)임을 보장하도록 명세가 변경되었으므로, 정렬 결과의 일관성 측면에서는 더욱 예측 가능해졌습니다.