n개 중 작은 k개 뽑기 방법질문있습니다. (시간복잡도!)

n개의 데이터 중 작은 순서대로 k개를 뽑는 알고리즘을 짜야합니다.

제가 생각해낸건

1. 힙트리를 k크기 만큼 만들어서 구축 -> 후에 나머지 n - k 개를 트리에 삽입

예상 시간복잡도 :
힙 트리 구축 - O(k) (선형시간에 가능하다고 알고있습니다.)
힙 트리 리빌딩 - (n-k) * O(log k)

= nlogk

2. 퀵 셀렉션 후 퀵 소트 1 패스 진행

예상 시간복잡도 :
퀵 셀렉션 - O(n)
퀵 셀렉션으로 뽑은 값(인덱스)를 피벗으로 삼고 퀵소트 1회 진행 - O(n)

= 2n = n

이 정도가 생각나는데... 틀린부분이 있을까요?
그리고 혹시 실제로 구현하면 숨어있는 상수가 많다거나 하는 이슈가 있을까요..?

그냥 언어에서 지원하는 짱빠른 소팅라이브러리 쓰는게 빠를거같기도하고..