1. 개요 a. 런(run): 원소들이 정렬되어 있는 순서 순차(ordered sequence) b. 합병 정렬: k개의 런(run)이 나뉘어진 n개이 언소들을 하나의 순서 순처로 합병하는 방식 -> 각 런은 key값에 따라 오름차순 정렬되어 있음 -> k개의 원소 중 가장 작은 키 값을 가진 원소를 선택: k-1번 비교 -> 선택트리 자료구조 이용 시 비교 회수 줄일 수 있음 2. 종류 a. 승리 트리(winner tree): 완전 이진트리 - 각 단말 노드는 런의 최소 키 값의 원소를 나타냄 - 내부 노드는 두 자식 중 가장 작은 키 값을 가진 원소로 나타남 - 구축과정: 가장 작은 키 값을 가진 원소가 승자, 트리에서 가장 작은 키 값을 가진 노드가 루트노드임으로 승자가됨 - 표현: 순차표현이 유리..