4번이 정답인 이유는, 입력 레코드를 정렬하기 위해 사용하는 비교 기반 정렬의 평균 시간 복잡도가 O(n log n)임을 보여줍니다. 이는 정렬 알고리즘의 기본 원리에 따라, 주어진 데이터의 수가 증가할수록 시간 복잡도가 급격히 증가하는 것을 나타냅니다. 즉, 최악의 경우에도 O(n²)의 시간복잡도보다 효율적이라는 점에서 중요한 의미를 가집니다.