JavaScript의 Sort 알고리즘 변화: QuickSort → TimSort

 

 

JavaScript의 Sort 알고리즘 변화: QuickSort → TimSort

📌 간단히 말하면
JavaScript의 `Array.sort()`가 사용하는 **정렬 알고리즘이 변경**되었습니다.

- **ES10 이전**: QuickSort (빠르지만 불안정할 수 있음)
- **ES10 이후**: TimSort (안정적이고 현실적으로 더 빠름)

---

🔄 QuickSort vs TimSort

QuickSort (과거)

장점: 평균적으로 매우 빠름 O(n log n)
단점: 
  - 최악의 경우 O(n²) 성능 저하
  - 같은 값의 순서가 바뀔 수 있음 (불안정)


**예시**: [3, 1, 3, 2] 정렬 후 첫 번째 3과 두 번째 3의 순서가 뒤바뀔 수 있음

 

TimSort (현재)

장점:
  - 최악의 경우에도 O(n log n) 보장
  - 같은 값의 원래 순서 유지 (안정적)
  - 실제 데이터에서 QuickSort보다 더 빠름
단점: 구현이 복잡함

💡 왜 TimSort로 바꿨나?

항목	QuickSort	TimSort
안정성	❌ 불안정	✅ 안정적
최악의 경우	O(n²) 😱	O(n log n) 🎯
실제 성능	평균적	더 좋음
실데이터 최적화	❌	✅ 정렬된/부분정렬된 데이터에 강함

📝 코드로 비교

// 안정성 테스트
const data = [
  { value: 3, id: 'A' },
  { value: 1, id: 'B' },
  { value: 3, id: 'C' },
  { value: 2, id: 'D' }
];

data.sort((a, b) => a.value - b.value);

// ES10+: 항상 id 'A'가 'C'보다 앞 (안정적) ✅
// ES10 이전: A와 C의 순서가 뒤바뀔 수 있음 (불안정) ❌

 🎯 정리

**TimSort는 현대적인 정렬 알고리즘으로**
- ✅ 데이터 순서 보장 (안정성)
- ✅ 최악의 경우에도 빠름
- ✅ 실제 상황에서 더 효율적

Python, Java 등도 이미 TimSort를 사용하고 있으며, JavaScript도 따라간 것입니다! 🚀