swift에서 sort() 어떤 알고리즘 쓸까?

Swift 에서 Sort()

swift로 작업을 하다가 보면 sort(), sortInPlace() 정렬을 많이 사용하게 됩니다.

그런데 우리가 자주 사용하는 저 sort()라는 녀석의 시간복잡도가 궁금해졌습니다.

먼저, 답은 O(n log n)

sort()는 어떤 알고리즘을 쓰는거지?

아래 swift 깃헙에서 컬렉션 알고리즘 쪽을 보면 어떤 알고리즘을 쓰는지 확인할수가 있는데요

https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionAlgorithms.swift.gyb

_introSort라는 녀석을 쓰고 있습니다.

자주들어본 퀵소트도, 힙소트도 아닌 그럼 IntroSort는 무엇인지 궁금해졌습니다.

IntroSort

IntroSort는 하이브리드 정렬의 한종류라고 합니다.

음 그럼 무엇을 하이브리드 했냐 봤더니, 퀵소트와 힙소트의 하이브리드라고 합니다.

퀵소트와 힙소트의 경우 시간복잡도 O(n log n) 형태이지만, 평균적으로 퀵소트가 더 빠르다고 알려져 있습니다.

대신 퀵소트의 경우 최악의 상황에서 (n^2) 로 알려져 있습니다.

퀵소트의 경우 재귀호출(분할정복)로 정렬하는 방식인데, 분할 횟수가 많아지면서 성능이 저하된다고 합니다. 그래서 IntroSort에서 분할 횟수가 특정 임계치에 도달하면 힙정렬로 스위칭해주는 방식을 사용한다고 합니다. IntroSort는 두개의 정렬의 장점을 결합한 형태라고 할수 있습니다.

결과적으로, IntroSort 경우에도 퀵소트와 힙소트와 같은 시간복잡도인 O(n log n)을 따릅니다.