[Naver D2] Tim sort

네이버 기술 블로그를 살펴보다가 Tim sort에 대한 이야기가 있어서 공부해보았다.

python sort 메소드가 Tim sort를 사용했다고는 알고 있었는데 그때 Team sort로 알고있었다.. 안찾아봐서..그냥 팀소트..쯤으로 알았다.

 

참고로 php sort 메소드는 quick sort를 사용하고 있다고 한다.

 

Start

위의 표를 살펴보았을 때 성능이 제일 좋아보이는 정렬 방식은 Heap sort와 Merge sort, Quick sort이다.

그렇게 생각한 이유는 시간복잡도가 다른 정렬 알고리즘에 비해 빠르기 때문인데,

항상 입력이 최선으로만 들어오지는 않기 때문에 평균 시간복잡도로 Heap Sort를 바라보았을 때..

 

O(nlogn)이라는 말은 실제 동작 시간이 C * nlogn + a(알파)라는 의미라고 한다.

이때, a(알파)는 상대적으로 무시할 수 있지만 nlogn에 곱해지는 상수 C는 큰 영향을 준다.

 

이 C 라는 값은 알고리즘이 참조 지역성 원리를 얼마나 잘 만족하는가 라고 한다.

참조 지역성 원리란, CPU가 미래에 원하는 데이터를 예측해서 속도가 빠른 장치인 캐시 메모리에 담아 놓는데

이때의 예측률을 높이기 위하여 사용하는 원리라고 한다.

 

쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다.

 

 

위와 같이 기존의 정렬 알고리즘들은 어떤 알고리즘이 탁월하게 좋다고 말하기가 쉽지 않았다.

상수 C의 값이 너무 커지지 않으면서 추가 메모리가 많이 필요치 않게, 최악의 경우에도 빠르게 동작하는 정렬 알고리즘에 대한 필요성이 보였다.