정렬 알고리즘 공부하다가 막혔는데요, 병합 정렬이랑 퀵 정렬 둘 다 평균 시간복잡도가 O(n log n)이라고 나와 있더라고요. 근데 실제로 라이브러리 정렬 구현 보면 퀵 정렬 계열(인트로소트 같은 거)을 많이 쓴다는 말도 있고, 또 어디선 병합 정렬이 안정적이라 좋다는 말도 있고... 도대체 뭐가 더 좋은 건가요?
제가 지금 이해한 걸 정리해보면 이 정도예요.
퀵 정렬 : 평균 O(n log n), 최악 O(n^2)
병합 정렬 : 항상 O(n log n)
여기서 헷갈리는 게, 퀵 정렬은 최악이 O(n^2)까지 터진다는데 그럼 병합 정렬이 더 안전한 거 아닌가요? 근데 왜 실무에선 퀵 정렬을 더 많이 쓴다는 거죠? 병합 정렬은 추가 메모리가 O(n) 필요하다는 것 때문에 그런 건가 싶기도 한데 확신이 안 서네요.
그리고 퀵 정렬 최악 O(n^2)가 실제로 잘 안 터진다고 하던데, 이미 정렬된 배열 넣으면 터지는 거 아니었나요? 피벗을 어떻게 잡느냐에 따라 다른 건가 싶고요. 대충 "상황 따라 다르다"는 답은 많이 봤는데, 구체적으로 어떤 상황에서 뭘 골라야 하는지 감이 안 잡혀서 질문 드려요. 정렬 개수가 몇 만 개 정도 되는 배열 정렬할 일이 있는데 이런 경우엔 뭘 쓰는 게 맞나요?