python 내장함수 list.sort() 의 정렬 방법??

코딩테스트를 풀다가 문득 궁금한점이 생겼다.

 

list.sort() << 바로 이건데

 

정렬에 종류에는 여러 방법이 있다. 삽입정렬, 버블정렬, 퀵정렬 등등 .. 

 

근데 파이썬에서는 과연 무슨 방법으로 정렬을 하는걸까??

 

그래서 우선 python 라이브러리를 찾아보려고 들어갔다.

 

파이썬 라이브러리들

OMG.. 절대 찾을 수 없다고 결론내렸다. 

 

그래서 스택오버플로우에 질문을 남겼다.

 

 

그래서 알게된 사실이 여러가지 있는데

 

1. list.sort()는 파이썬 내장 파일이기때문에 C언어로 구현되어 있고 저 위에 라이브러리 파일에선 찾을 수 없다.

2. 사용되는 알고리즘은 팀 피터라는 사람이 만든 tim sort를 사용했다.

3. 실제 코드는 여기있으니까 참고해라 

https://github.com/python/cpython/blob/ba18c0b13ba3c08077ea3db6658328523823a33f/Objects/listobject.c#L1051

python/cpython

파이썬 정렬 알고리즘을 만든 Tim Peters 

 

 

코드부분을 좀 보고싶었는데 '아 이거 건드리면 x되겠다.' 라는 생각이 들어 일단 킵 해놨다.

 

여러가지 글을 보니 병합정렬과 삽입정렬을 적절히 섞은 알고리즘이라고 하고 시간복잡도는 O(NlogN)이라고한다.

그래서 많은 사람들이 다른 일반적인 정렬보다 빠르니까 정렬할 땐 파이썬 내장함수인 sort()를 추천한다고 한다.

 

또 python이 c로 만들어져있다는 사실을 다시 생각하게됐다.