[정보처리기사] 실기 2장 데이터 입출력 구현

데이터베이스 개요

• 데이터저장소: 데이터들을 논리적인 구조로 조직화하거나, 물리적인 공간에 구축한 것을 의미한다.
• 데이터베이스: 여러 사람에 의해 공동으로 사용될 데이터를 중복을 배제하여 통합하고, 쉽게 접근하여 처리할 수 있도록 저장장치에 저장하여 항상 사용할 수 있도록 운영하는 운영 데이터이다.

DBMS(DataBase Management System)

• 사용자의 요구에 따라 정보를 생성해주고, 데이터베이스를 관리해주는 소프트웨어이다.
• DBMS의 필수 기능 3가지
  • 정의(Definition) 기능: 데이터의 형(Type)과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능
  • 조작(Manipulation) 기능: 데이터 검색, 갱신, 삭제 등을 위해 인터페이스 수단을 제공하는 기능
  • 제어(Control) 기능: 데이터의 무결성, 보안, 권한 검사, 병행 제어를 제공하는 기능

데이터의 독립성

• 데이터의 독립성은 종속성에 대비되는 말로 논리적 독립성과 물리적 독립성이 있다.
  • 논리적 독립성: 응용 프로그램과 데이터베이스를 독립시킴으로써, 데이터의 논리적 구조를 변경시키더라도 응용 프로그램은 영향을 받지 않음
  • 물리적 독립성: 응용 프로그램과 보조기억장치 같은 물리적 장치를 독립시킴으로써, 디스크를 추가/변경하더라도 응용 프로그램은 영향을 받지 않음

스키마(Schema)

• 데이터베이스의 구조와 제약조건에 관한 전반적인 명세를 기술한 것이다.
  • 외부 스키마: 사용자나 응용 프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조를 정의한 것
  • 개념 스키마: 데이터베이스의 전체적인 논리적 구조로, 모든 응용 프로그램이나 사용자들이 필요로 하는 데이터를 종합한 조직 전체의 데이터베이스로 하나만 존재함
  • 내부 스키마: 물리적 저장장치의 입장에서 본 데이터베이스의 구조로, 실제로 저장될 레코드의 형식, 저장 데이터 항목의 표현 방법, 내부 레코드의 물리적 순서 등을 나타냄

데이터베이스 설계

설계시 고려사항

• 무결성: 삽입, 삭제, 갱신 등의 연산 후에도 데이터베이스에 저장된 데이터가 정해진 제약 조건을 항상 만족해야 함
• 일관성: 데이터베이스에 저장된 데이터들 사이나, 특정 질의에 대한 응답이 처음부터 끝까지 변함없이 일정해야 함
• 회복: 시스템에 장애가 발생했을 때 장애 발생 직전의 상태로 복구할 수 있어야 함
• 보안: 불법적인 데이터의 노출 또는 변경이나 손실로부터 보호할 수 있어야 함
• 효율성: 응답시간의 단축, 시스템의 생산성, 저장 공간의 최적화 등이 가능해야 함
• 데이터베이스 확장: 데이터베이스 운영에 영향을 주지 않으면서 지속적으로 데이터를 추가할 수 있어야 함

설계 순서

1. 요구 조건 분석: 데이터베이스 용도 파악 및 요구 조건 명세서 작성
2. 개념적 설계(정보 모델링, 개념화): 개념 스키마 설계, 트랜잭션 모델링, E-R 다이어그램 작성
3. 논리적 설계(데이터 모델링): 논리 스키마 설계, 트랜잭션 인터페이스 설계, DBMS에 맞는 논리적 자료 구조로 변환(mapping)
4. 물리적 설계(데이터 구조화): 논리적 구조로 표현된 데이터를 물리적 구조의 데이터로 변환
5. 구현: 데이터베이스 생성, 트랜잭션 작성

데이터 모델

• 현실 세계의 정보들을 컴퓨터에 표현하기 위해서 단순화, 추상화하여 체계적으로 표현한 개념적 모형이다.
• 데이터 모델 구성 요소: 개체, 속성, 관계
• 데이터 모델 종류: 개념적 데이터 모델, 논리적 데이터 모델, 물리적 데이터 모델
  • 개념적 데이터 모델: 현실 세계에 대한 인식을 추상적 개념으로 표현하는 과정
  • 논리적 데이터 모델: 개념적 모델링 과정에서 얻은 개념적 구조를 컴퓨터 세계의 환경에 맞도록 변환하는 과정 (데이터 모델 = 논리적 데이터 모델)
• 데이터 모델에 표시할 요소: 구조, 연산, 제약 조건
  • 구조(Structure): 논리적으로 표현된 개체 타입들 간의 관계로서 데이터 구조 및 정적 성질 표현
  • 연산(Operation): 데이터베이스에 저장된 실제 데이터를 처리하는 작업에 대한 명세로서 데이터베이스를 조작하는 기본 도구
  • 제약 조건(Contraint): 데이터베이스에 저장될 수 있는 실제 데이터의 논리적인 제약 조건

데이터 모델의 구성 요소

• 개체(Entity)
  • 데이터베이스에 표현하려는 것으로, 사람이 생각하는 개념이나 정보 단위 같은 현실 세계의 대상체이다.
  • 독립적으로 존재하거나 그 자체로서도 구별이 가능하며, 유일한 식별자에 의해 식별된다.
  • 다른 개채와 하나 이상의 관계가 있다.
• 속성(Attribute)
  • 데이터베이스를 구성하는 가장 작은 논리적 단위이다.
  • 개체를 구성하는 항목으로 개체의 특성을 기술한다.
  • 속성의 차수(Degree)라고 한다.
  • 속성은 속성의 특성과 개체 구성 방식에 따라 분류한다
    • 속성의 특성에 의한 속성 분류: 기본 속성, 설계 속성, 파생 속성
    • 개체 구성 방식에 따른 분류: 기본키 속성, 외래키 속성, 일반 속성
• 관계(Relationship)
  • 개체와 개체 사이의 논리적인 연결을 의미한다.
  • 관계에는 개체 간의 관계와 속성 간의 관계가 있다.
  • 관계의 형태
    • 일 대 일(1:1), 일 대 다(1:N), 다 대 다(N:N)
  • 관계의 종류
    • 종속 관계, 중복 관계, 재귀 관계, 배타 관계

식별자(Identifier)

• 하나의 개체 내에서 각각의 인스턴스를 유일하게 구분할 수 있는 구분자이다.
• 모든 개체는 한 개 이상의 식별자를 반드시 가져야 한다.
• 식별자의 분류: 주 식별자 / 보조 식별자, 내부 식별자 / 외부 식별자, 단일 식별자 / 복합 식별자, 원조 식별자 / 대리 식별자
• 주 식별자의 특징
  • 유일성: 개체 내의 모든 인스턴스들은 주 식별자에 의해 유일하게 구분되어야 함
  • 최소성: 유일성을 만족시키기에 필요한 최소한의 속성으로만 구성되어야 함
  • 불변성: 주 식별자가 특정 개체에 한 번 지정되면 그 식별자는 변하지 않아야 함
  • 존재성: 주 식별자가 지정되면 식별자 속성에 반드시 데이터 값이 존재해야 함

E-R(개체-관계) 모델

• 개체와 개체 간의 관계를 기본 요소로 이용하여 현실 세계의 무질서한 데이터를 개념적인 논리 데이터로 표현하기 위한 방법이다.
• 개념적 데이터 모델의 가장 대표적인 것이다.
• 개체 타입(Entity Type)과 이들 간의 관계 타입(Relationship Type)을 이용해 현실 세계를 개념적으로 표현한다.

관계형 데이터베이스

• 2차원적인 표를 이용해서 데이터 상화 관계를 정의하는 데이터베이스이다.
• 개체와 관계를 모두 릴레이션이라는 표로 표현하기 때문에 개체를 표현하는 개체 릴레이션과 관계를 표현하는 관계 릴레이션이 존재한다.

관계형 데이터베이스의 구조

• 릴레이션(Relation)은 데이터들을 표의 형태로 표현한 것으로, 구조를 나타내는 릴레이션 스키마와 실제 값들인 릴레이션 인스턴스로 구성된다.

예시) <학생> 릴레이션

학번	이름	학년	성별	학과
2012345678	김예소	2	여	CD
2012345679	고강민	1	남	CD
2012345670	이향기	4	여	ID

• 튜플(Tuple)
  • 릴레이션을 구성하는 각각의 행
  • 속성의 모임으로 구성
  • 튜플의 수: 카디널리티(Cardinality) 또는 기수
  • 예시) (2012345678, 김예소, 2, 여, CD), ...
• 속성(Attribute)
  • 데이터베이스를 구성하는 가장 작은 논리적 단위
  • 개체의 특성을 기술
  • 속성의 수: 디그리(Degree) 또는 차수
  • 예시) 학번, 이름, 학년, 성별, 학과
• 도메인(Domain)
  • 하나의 속성이 취할 수 있는 같은 타입의 원자값들의 집합
  • 예시) 성별 속성의 도메인: "남", "여"

릴레이션의 특징

• 한 릴레이션에는 똑같은 튜플이 포함될 수 없다.
• 튜플 사이에는 순서가 없다.
• 튜플들의 삽입, 삭제 등의 작업으로 인해 릴레이션은 시간에 따라 변한다.
• 속성의 순서는 중요하지 않다.
• 릴레이션을 구성하는 튜플을 유일하게 식별하기 위해 속성들의 부분집합을 키(Key)로 설정한다.
• 속성의 값은 논리적으로 더 이상 쪼갤 수 없는 원자값만을 저장한다.

관계형 데이터베이스의 제약 조건 - 키(Key)

• 키는 데이터베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 기준이 되는 속성을 말한다.
• 키의 종류: 후보키, 기본키, 대체키, 슈퍼키, 외래키

후보키(Candidate Key)

• 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용되는 속성들의 부분집합이다.
• 기본키로 사용할 수 있는 속성들을 말한다.
• 후보키는 유일성과 최소성을 모두 만족시켜야 한다.
  • 유일성: 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있어야 함
  • 최소성: 키를 구성하는 속성 하나를 제거하면 유일하게 식별할 수 없도록 꼭 필요한 최소의 속성으로 구성되어야 함

기본키(Primary Key)

• 후보키 중에서 특별히 선정된 키이다.
• 중복된 값을 가질 수 없다.
• 특정 튜플을 유일하게 구별할 수 있는 속성이다.
• NULL값을 가질 수 없다.

대체키(Alternate Key)

• 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키를 의미한다.
• 보조키라고도 한다.

슈퍼키(Super Key)

• 한 릴레이션 내에 있는 속성들의 집합으로 구성된 키를 말한다.
• 릴레이션을 구성하는 모든 튜플 중 슈퍼키로 구성된 속성의 집합과 동일한 값은 나타나지 않는다.
• 모든 튜플에 대해 유일성은 만족하지만, 최소성은 만족하지 못한다.

외래키(Foreign Key)

• 다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합을 의미한다.
• 외래키로 지정되면 참조 릴레이션의 기본키에 없는 값은 입력할 수 없다.

관계형 데이터베이스의 제약 조건 - 무결성(Integrity)

• 무결성은 데이터베이스에 저장된 데이터 값과 그것이 표현하는 현실 세계의 실제값이 일치하는 정확성을 의미한다.
• 데이터베이스에 들어 있는 데이터의 정확성을 보장하기 위해 부정확한 자료가 저장되는 것을 방지하기 위한 제약 조건을 말한다.
• 무결성의 종류: 개체 무결성, 참조 무결성, 도메인 무결성, 사용자 정의 무결성, NULL 무결성, 고유 무결성, 키 무결성, 관계 무결성

관계대수 및 관계해석

관계대수

• 관계형 데이터베이스에서 원하는 정보와 그 정보를 검색하기 위해서 어떻게 유도하는가를 기술하는 절차적인 언어이다.
• 릴레이션을 처리하기 위해 연산자와 연산규칙을 제공하며, 피연산자와 연산 결과가 모두 릴레이션이다.

순수 관계 연산자

• Select
  • 선택 조건을 만족하는 튜플의 부분집합을 구하여 새로운 릴레이션을 만드는 연산
  • 행에 해당하는 튜플을 구하는 것이므로 수평 연산이라고도 함
  • 기호: σ(시그마)
• Project
  • 속성 리스트에 제시된 속성 값만을 추출하여 새로운 릴레이션을 만드는 연산
  • 열에 해당하는 속성을 추출하는 것이므로 수직 연산이라고도 함
  • 기호: π(파이)
• Join
  • 공통 속성을 중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 연산
  • Join의 결과는 Cartesian Product(교차곱)를 수행한 다음 Select를 수행한 것과 같음
  • 기호: ⋈
• Division
  • X ⊃ Y 인 두 개의 릴레이션 R(X)와 S(Y)가 있을 때, R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구하는 연산
  • 기호: ÷

일반 집합 연산자

• Union
  • 두 릴레이션에 존재하는 튜플의 합집합을 구하되, 중복되는 튜플은 제거되는 연산
  • 기호: ∪
• Intersection
  • 두 릴레이션에 존재하는 튜플의 교집합을 구하는 연산
  • 기호: ∩
• Difference
  • 두 릴레이션에 존재하는 튜플의 차집합을 구하는 연산
  • 기호: －
• Cartesian Product
  • 두 릴레이션에 있는 튜플들의 순서쌍을 구하는 연산
  • 기호: ×

관계해석(Relational Calculus)

• 관계 데이터의 연산을 표현하는 방법이다.
• 원하는 정보가 무엇이라는 것만 정의하는 비절차적 특성을 지닌다.
• 원하는 정보를 정의할 때는 계산 수식을 사용한다.

이상(Anomaly)

• 테이블에서 일부 속성들의 종속으로 인해 데이터의 중복이 발생하고, 이 중복(Redundancy)으로 인해 테이블 조작 시 문제가 발생하는 현상을 의미한다.
• 이상의 종류: 삽입 이상, 삭제 이상, 갱신 이상
  • 삽입 이상(Insertion Anomaly): 테이블에 데이터를 삽입할 때 의도와는 상관없이 원하지 않는 값들로 인해 삽입할 수 없게 되는 현상이다.
  • 삭제 이상(Deletion Anomaly): 테이블에서 한 튜플을 삭제할 때 의도와는 상관없는 값들도 함께 삭제되는, 즉 연쇄 삭제가 발생하는 현상이다.
  • 갱신 이상(Update Anomaly): 테이블에서 튜플에 있는 속성 값을 갱신할 때 일부 튜플의 정보만 갱신되어 정보에 불일치성(Inconsistency)이 생기는 현상이다.

정규화와 반정규화

정규화(Normalization)

• 테이블의 속성들이 상호 종속적인 관계를 갖는 특성을 이용하여 테이블을 무손실 분해하는 과정이다.
• 정규화의 목적은 가능한 한 중복을 제거하여 삽입, 삭제, 갱신 이상의 발생 가능성을 줄이는 것이다.
• 정규화 과정: 비정규 릴레이션 > (도메인이 원자값) > 1NF > (부분적 함수 종속 제거) > 2NF > (이행적 함수 종속 제거) > 3NF > (결정자이면서 후보키가 아닌 것 제거) > BCNF > (다치 종속 제거) > 4NF > (조인 종속성 이용) > 5NF
  • 제 1정규형: 모든 속성의 도메인이 원자 값만으로 되어 있는 정규형
  • 제 2정규형: 제 1정규형이고, 기본키가 아닌 모든 속성이 기본키에 대하여 완전 함수적 종속을 만족하는 정규형
  • 제 3정규형: 제 2정규형이고, 기본키가 아닌 모든 속성이 기본키에 대해 이행적 함수적 종속을 만족하지 않는 정규형
  • BCNF: 모든 결정자가 후보키인 정규형
  • 제 4정규형: 다중 값 종속 A->->B가 존재할 경우 테이블의 모든 속성이 A에 함수적 종속 관계를 만족하는 정규형
  • 제 5정규형: 모든 조인 종속이 테이블의 후보키를 통해서만 성립되는 정규형

반정규화(Denormalization)

• 시스템의 성능을 향상하고 개발 및 운영의 편의성 등을 높이기 위해 정규화된 데이터 모델을 의도적으로 통합, 중복, 분리하여 정규화 원칙을 위배하는 행위이다.
• 반정규화를 수행하면 시스템의 성능이 향상되고 관리 효율성은 증가하지만 데이터의 일관성 및 정합성이 저하될 수 있다.
• 반정규화의 방법: 테이블 통합, 테이블 분할, 중복 테이블 추가, 중복 속성 추가

트랜잭션(Transaction)

• 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미한다.
• 데이터베이스 시스템에서 병행 제어 및 회복 작업 시 처리되는 작업의 논리적 단위로 사용된다.

트랜잭션의 특징

• 원자성(Atomicity): 트랜잭션의 연산은 데이터베이스에 모두 반영되도록 완료(Commit)되든지 아니면 전혀 반영되지 않도록 복구(Rollback)되어야 함
• 일관성(Consistency): 트랜잭션이 그 실해을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함
• 독립성(Isolation): 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행 중에 다른 트랜잭션의 연산이 끼어들 수 없음
• 영속성(Durability): 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 함

인덱스(Index)

• 데이터 레코드를 빠르게 접근하기 위해 <키 값, 포인터> 쌍으로 구성되는 데이터 구조이다.
• 레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다.
• 레코드의 삽입과 삭제가 수시로 일어나는 경우에는 인덱스의 개수를 최소로 하는 것이 효율적이다.

뷰(View)

• 사용자에게 접근이 허용된 자료만을 제한적으로 보여주기 위해 하나 이상의 기본 테이블로부터 유도된, 이름을 가지는 가상 테이블이다.
• 저장장치 내에 물리적으로 존재하지 않지만, 사용자에게는 있는 것처럼 간주된다.
• 뷰를 통해서만 데이터에 접근하게 하면 뷰에 나타나지 않는 데이터를 안전하게 보호하는 효율적인 기법으로 사용할 수 있다.
• 뷰의 장점
  • 논리적 데이터 독립성을 제공함
  • 동일 데이터에 대해 동시에 여러 사용자의 상이한 응용이나 요구를 지원해 줌
  • 사용자의 데이터 관리를 간단하게 해줌
  • 접근 제어를 통한 자동 보안이 제공됨
• 뷰의 단점
  • 독립적인 인덱스를 가질 수 없음
  • 뷰의 정의를 변경할 수 없음
  • 뷰로 구성된 내용에 대한 삽입, 삭제, 갱신 연산에 제약이 따름

데이터베이스 보안

• 데이터베이스의 일부 또는 전체에 대해서 권한이 없는 사용자가 액세스하는 것을 금지하기 위해 사용되는 기술이다.
• 보안을 위한 데이터 단위는 테이블 전체로부터 특정 테이블의 특정 행과 열에 있는 데이터 값에 이르기까지 다양하다.

암호화(Encryption)

• 데이터를 보낼 때 송신자가 지정한 수신자 이외에는 그 내용을 알 수 없도록 평문을 암호문으로 변환하는 것이다.
• 암호화 기법
  • 개인키 암호 방식(Private Key Encryption)
  • 공개키 암호 방식(Public Key Encryption)

접근통제

• 데이터가 저장된 객체와 이를 사용하려는 주체 사이의 정보 흐름을 제한하는 것이다.
• 접근통제 3요소
  • 접근통제 정책
  • 접근통제 메커니즘
  • 접근통제 보안 모델

자료구조

• 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.
• 저장 공간의 효율성과 실행시간의 단축을 위해 사용한다.

배열(Array)

• 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합이다.
• 반복적인 데이터 처리 작업에 적합한 구조이다.
• 정적인 자료 구조로, 기억장소의 추가가 어렵다.

연속 리스트(Contiguous List)

• 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.
• 삽입/삭제 시 자료의 이동이 필요하다.

연결 리스트(Linked List)

• 자료들을 임의의 기억광간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 기억 공간의 이용 효율이 좋지 않다.
• 접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어렵다.

스택(Stack)

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
• 후입선출(Last In First Out) 방식으로 자료를 처리한다.
• 오버플로, 언더플로가 발생한다.

큐(Queue)

• 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조이다.
• 선입선출(First In First Out) 방식으로 처리한다.

그래프(Graph)

• 정점(Vertex)과 간선(Edge)의 두 집합으로 이루어지는 자료 구조이다.
• 사이클이 없는 그래프를 트리라 한다.
• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.

트리(Tree)

• 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다.
• 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것
• 근 노드(Root Node): 트리의 맨 위에 있는 노드
• 차수(Degree): 각 노드에서 뻗어나온 가지의 수
• 단말 노드(Terminal Node, Leaf Node): 자식이 하나도 없는 노드
• 비단말 노드(Non-Terminal Node): 자식이 하나라도 있는 노드

이진 트리

• 차수가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리를 말한다.
• 트리의 운행법
  • Preorder 운행: Root -> Left -> Right
  • Inorder 운행: Left -> Root -> Right
  • Postorder 운행: Left -> Right -> Root

정렬(Sort)

삽입 정렬(Insertion Sort)

• 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식이다.
• 시간 복잡도: 평균과 최악 모두 $O(N^2)$

선택 정렬(Selection Sort)

• n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.
• 시간 복잡도: 평균과 최악 모두 $O(N^2)$

버블 정렬(Bubble Sort)

• 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다.
• 시간 복잡도: 평균과 최악 모두 $O(N^2)$

퀵 정렬(Quick Sort)

• 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해 시키는 과정을 반복하는 정렬 방식이다.
• 시간 복잡도: 평균 $O(Nlog_2N)$, 최악 $O(N^2)$

힙 정렬(Heap Sort)

• 전이진 트리를 이용한 정렬 방식이다.
• 시간 복잡도: 평균과 최악 모두 $O(Nlog_2N)$

2-way 합병 정렬(Merge Sort)

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다.
• 시간 복잡도: 평균과 최악 모두 $O(Nlog_2N)$