[기술 면접] 2026-04-23 — 정렬 알고리즘 비교와 선택 기준

오늘의 면접 주제

 

developer-roadmap 같은 학습 트렌드와 맞물려, 정렬 알고리즘은 여전히 자료구조·알고리즘 면접의 기본 질문으로 자주 나온다.

핵심 한 줄 요약

정렬 알고리즘 면접의 핵심은 이름을 외우는 것이 아니라, 데이터 특성과 요구사항에 따라 왜 QuickSort, MergeSort, HeapSort, TimSort 중 하나를 선택하는지 설명하는 것이다.

면접 질문 & 모범 답변

Q1. 정렬 알고리즘에서 가장 먼저 봐야 할 기준은 무엇인가요?

기본 답변: 시간 복잡도만 보면 부족합니다. 실제로는 평균 성능, 최악 성능, 추가 메모리 사용, 안정 정렬 여부를 함께 봐야 합니다. 면접에서는 "무조건 빠른 정렬"보다 "상황에 맞는 정렬"을 설명하는 것이 중요합니다.
심화 포인트: 같은 O(n log n)이어도 동작 방식이 다릅니다. 예를 들어 MergeSort는 안정적이지만 메모리를 더 쓰고, HeapSort는 메모리를 적게 쓰지만 실제 구현과 상수 비용 면에서 덜 선호될 수 있습니다.

Q2. QuickSort는 왜 빠르다고 하나요?

기본 답변: QuickSort는 pivot을 기준으로 데이터를 둘로 나누고, 각 구간을 재귀적으로 정렬합니다. 평균적으로 분할이 균형 있게 되면 O(n log n)이 나오고, 메모리 접근도 비교적 효율적이라 실제 실행 속도가 빠른 편입니다.
심화 포인트: 최악의 경우는 O(n^2)입니다. 이미 정렬된 데이터에서 pivot을 잘못 고르면 계속 한쪽으로만 쏠리기 때문입니다. 그래서 실무 구현은 random pivot이나 median-of-three 같은 방식을 자주 씁니다.

Q3. MergeSort와 QuickSort는 어떻게 비교하나요?

기본 답변: MergeSort는 항상 O(n log n)을 보장하고 안정 정렬입니다. 대신 병합할 때 추가 배열이 필요해서 메모리를 더 씁니다. QuickSort는 평균 성능이 좋고 in-place에 가깝지만 최악 성능이 나빠질 수 있고 기본 구현은 불안정 정렬입니다.
심화 포인트: "언제 어떤 걸 쓰겠냐"가 중요합니다. 예를 들어 레코드 정렬에서 같은 키의 기존 순서를 유지해야 하면 MergeSort 계열이 더 적합합니다.

Q4. HeapSort는 실무에서 왜 상대적으로 덜 보이나요?

기본 답변: HeapSort는 최악에도 O(n log n)이고 추가 메모리가 거의 필요 없습니다. 이론적으로는 균형이 좋습니다. 하지만 캐시 친화성이 떨어지고, 실제 성능이 QuickSort나 TimSort보다 불리한 경우가 많아 일반 애플리케이션 코드에서는 덜 선택됩니다.
심화 포인트: HeapSort는 "성능 절대값"보다 "최악 성능 보장"이 중요한 환경에서 의미가 있습니다. 즉, 면접에서는 장점이 적은 알고리즘이 아니라, 우선순위가 다른 알고리즘으로 이해해야 합니다.

Q5. 안정 정렬과 불안정 정렬은 왜 중요한가요?

기본 답변: 안정 정렬은 같은 값을 가진 원소들의 기존 순서를 유지합니다. 예를 들어 사원 목록을 먼저 이름으로 정렬한 뒤, 부서 기준으로 다시 정렬할 때 안정 정렬이면 이름 순서가 유지됩니다.
심화 포인트: 많은 주니어가 "같은 값이면 순서가 바뀌어도 상관없지 않나"라고 생각합니다. 하지만 실제 서비스에서는 다중 조건 정렬이 많아서 안정성은 결과의 예측 가능성과 연결됩니다.

[js][{id:1, age:20}, {id:2, age:20}]

Q6. TimSort는 왜 많이 쓰이나요?

기본 답변: TimSort는 MergeSort와 Insertion Sort의 장점을 섞은 하이브리드 정렬입니다. 현실 데이터가 완전히 랜덤하지 않고 일부 정렬된 구간을 가진 경우가 많다는 점을 활용합니다. 그래서 Python, Java의 일부 정렬 구현에서 사용됩니다.
심화 포인트: TimSort의 핵심은 "현실 데이터 최적화"입니다. 면접에서 이 말을 할 수 있으면 단순 암기가 아니라 실제 사용 배경을 이해한 것으로 보입니다.

Q7. 거의 정렬된 데이터라면 어떤 정렬이 유리한가요?

기본 답변: 이런 경우 Insertion Sort나 TimSort가 유리할 수 있습니다. 이미 많이 정렬된 상태라면 원소 이동이 적어서 오히려 단순한 알고리즘이 빠르게 끝날 수 있습니다.
심화 포인트: 알고리즘 선택은 Big-O만으로 끝나지 않습니다. 입력 데이터의 분포를 모르면 좋은 답을 하기 어렵습니다.

꼬리 질문 대비

QuickSort에서 pivot을 어떻게 고를 건가요?
안정 정렬이 꼭 필요한 실무 사례를 말해보세요.
언어 표준 라이브러리 정렬이 왜 직접 구현보다 자주 쓰이나요?
메모리가 제한된 환경이라면 어떤 정렬을 고려하겠나요?
O(n log n)이 같아도 실제 속도가 다른 이유는 무엇인가요?

헷갈리기 쉬운 포인트

안정 정렬과 in-place 정렬은 다른 개념입니다. 안정성은 순서 유지이고, in-place는 추가 메모리 사용과 관련 있습니다.
QuickSort는 항상 빠른 정렬이 아닙니다. 평균적으로 빠르지만 최악은 O(n^2)입니다.
HeapSort는 이론적으로 균형 잡혀 있어도 실무 기본 선택지는 아닙니다. 실제 성능과 구현 선호도가 다르기 때문입니다.

면접관 시각

이 주제에서는 알고리즘 이름을 몇 개 외웠는지보다, 선택 기준을 말할 수 있는지를 봅니다. 특히 안정 정렬, 최악 시간 복잡도, 추가 메모리, 실제 라이브러리 선택 이유를 연결해서 설명하면 좋은 평가를 받습니다. 반대로 O(n log n)만 반복하면 개념은 알지만 실무 감각은 약하다고 판단하기 쉽습니다.