정렬이란?
파일을 구성하는 각 레코드(Record)를 특정 키 항목을 기준으로 오름차순과 내림차순으로 재배열하는 작업을 말한다.

정렬기법 두 가지
내부정렬과 외부정렬

내부정렬기법이란?
자료량이 적을 때 주기억 장치 내에서 정렬하는 방법이다. 속도는 빠르나 정렬할 자료의 양이 많을 경우 부적합하다.

내부정렬의 종류
삽입 정렬(Insertion Sort) : 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치한다.
선택 정렬(Select Sort) : 레코드의 최소값을 찾아 첫 번째 위치에 놓고 다음 최소값을 찾아 두 번째 위치에 놓는 방법을 반복하여 정렬한다.
거품 정렬(Bubble Sort) : 인접한 값과 비교하여 정렬하는 방식이다. 끝에 값부터 시작한다.
2-Way 합병 정렬(Merge Sort) : 값들을 2개씩 묶어가면서 비교하여 정렬한다.
퀵 정렬(Quick Sort) : 맨 뒤의 원소를 기준 원소로 잡고, 기준 원소보다 작은 수는 기준의 왼쪽, 나머지는 오른쪽으로 정렬하는 기법이다.
힙 정렬(Heap Sort) : 최대값을 갖는 요소를 추출해서 오름차순 정렬한다.

외부정렬기법이란?
대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법이다. 속도는 느리지만 자료의 양이 많은 경우 효과적이다.

외부정렬의 종류
교대식 합병정렬(Oscillating Merge Sort) : 테이프의 읽기 쓰기 기능이 역방향과 순방향이 다 가능한 테이프 장치의 기능을 이용한다.
계단식 합병정렬(Cascade Merge Sort) : 부분적으로 정렬된 서브파일들을 한 개의 빈 테이프에 병합해 정렬하는 방법을 반복 시행한다.
다상 합병정렬(Polyphase Merge Sort) : 분산 수록되는 레코드의 수를 피보나치 수열을 이용 하여 레코드를 분산 수록하여 정렬한다.
균형 합병정렬(Balance Merge Sort) : 1개의 테이프 장치가 주어지면 각 테이프에는 똑같은 크기의 레코드들이 반씩 나누어져 내부 방법을 통해 정렬한다.

교환 방식에 따른 정렬
직접 정렬 : 레코드 전체를 이용하여 정렬한다.
간접 정렬 : 별도 존재하는 키 값의 인덱스 만 정렬한다.