정렬 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

정렬 알고리즘은 컴퓨터 과학에서 효율적인 데이터 정렬을 위한 핵심 연구 분야로, 다양한 알고리즘이 개발되어 왔다. 1950년대부터 연구가 시작되어, 초기의 거품 정렬을 비롯하여 2000년대에 개발된 팀소트와 라이브러리 소트 등 다양한 알고리즘이 존재한다. 정렬 알고리즘은 컴퓨터 과학 입문 수업에서 자료 구조, 알고리즘 분석 등 핵심 개념을 설명하는 데 활용된다.

정렬 알고리즘은 안정성, 계산량, 내부/외부 정렬 여부에 따라 분류된다. 안정 정렬은 동일한 키 값을 가진 레코드의 상대적 순서를 유지하며, 여러 번 정렬을 수행할 때 유용하다. 계산량은 입력 데이터의 크기 n에 따라 달라지며, 비교 정렬은 최소 O(n log n)의 비교 횟수를 필요로 한다. 내부 정렬은 데이터가 주기억장치에 저장되는 경우, 외부 정렬은 보조 기억 장치에 저장되는 경우에 사용된다.

정렬 알고리즘에는 비교 정렬과 비교가 아닌 정렬이 있으며, 비교 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬, 삽입 정렬 등이 있다. 비교가 아닌 정렬에는 계수 정렬, 버킷 정렬, 기수 정렬 등이 있다. 실용적인 구현에서는 작은 데이터에는 삽입 정렬, 큰 데이터에는 힙 정렬, 합병 정렬 또는 퀵 정렬을 사용하는 하이브리드 알고리즘이 널리 사용된다.

더 읽어볼만한 페이지

데이터 처리 - 정렬
정렬은 데이터를 특정 기준에 따라 순서대로 배열하는 과정으로, 검색 및 병합 알고리즘의 효율성을 높이고, 정의된 순서로 데이터 처리를 가능하게 하며, 오름차순과 내림차순으로 나뉘고, 컴퓨터 과학과 다양한 산업 분야에서 활용된다.
데이터 처리 - 데이터 유효성 검사
데이터 유효성 검사는 데이터의 정확성, 완전성, 유효성을 보장하기 위해 다양한 유형의 검사를 수행하고, 그 결과에 따라 시정 조치를 취하여 데이터 손상 및 보안 취약점을 방지하는 절차이다.
정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.

정렬 알고리즘
개요
퀵 정렬 알고리즘의 애니메이션
범주	정렬 알고리즘
자료 구조	배열
시간 복잡도
최악의 경우	O(n^2)
최선의 경우	O(n log n) 또는 O(n)
평균적인 경우	O(n log n)
공간 복잡도
최악의 경우	O(n) 총합, O(log n) 보조
평균	O(log n)
정렬 기준
제자리 정렬인가	예
안정적인가
안정적인 정렬인가	아니오
발견자
발견자	존 폰 노이만
첫 번째 발표
발표 연도	1945년

2. 역사

컴퓨팅의 시작부터 정렬 알고리즘은 단순한 목표에도 불구하고 효율적으로 실행하기 위한 복잡성 때문에 상당한 연구가 이루어져 왔다. 1951년경 초기 정렬 알고리즘 개발자 중에는 에니악(ENIAC)과 유니박(UNIVAC) 개발에 참여했던 베티 홀버튼(Betty Holberton)이 있었다.^[46]^[47]^[1]^[2] 거품 정렬은 1956년 이전에 분석되었다.^[48]^[3]

비교 정렬 알고리즘은 기본적으로 Ω(''n'' log ''n'') 비교의 시간 복잡도 하한을 가진다. 즉, 일부 입력에 대해서는 정렬할 배열 요소 수 ''n''에 대해 ''n'' log ''n''에 비례하는 횟수 이상의 비교가 필요하다. 반면 계수 정렬과 같이 비교에 기반하지 않는 알고리즘은 특정 조건 하에서 더 나은 성능을 보일 수 있다. 점근적으로 최적인 정렬 알고리즘들은 20세기 중반부터 알려졌으며, 이후에도 유용하고 새로운 알고리즘들이 계속 개발되고 있다. 예를 들어 현재 널리 사용되는 팀소트(Timsort)는 2002년에 개발되었고, 라이브러리 소트(Library sort)는 2006년에 처음 발표되었다.^[1]^[2] (일부 자료에서는 2004년으로 언급)

정렬 알고리즘은 컴퓨터 과학 입문 수업에서 중요한 주제로 다루어진다. 다양한 정렬 알고리즘들을 통해 점근 표기법(빅 오 표기법 포함), 분할 정복 알고리즘, 힙이나 이진 트리와 같은 자료 구조, 확률적 알고리즘, 최선, 최악, 그리고 평균의 경우 분석, 타임스페이스 트레이드오프, 하한 및 상한 등 컴퓨터 과학의 핵심 개념들을 자연스럽게 소개하고 학습할 수 있기 때문이다.

작은 크기의 배열을 최적으로(가장 적은 비교 및 교환 횟수로) 또는 빠르게(특정 하드웨어 환경에 맞춰) 정렬하는 방법이나, 병렬 컴퓨팅 환경에서 최적의 정렬 방법을 찾는 것은 여전히 활발한 연구 주제이다.

정렬된 데이터는 탐색이나 병합처럼 정렬된 입력을 요구하는 다른 알고리즘의 효율성을 높이는 데 중요하며, 사람이 데이터를 이해하고 확인하기에도 더 용이하다. 정렬 알고리즘의 결과는 다음 두 가지 조건을 만족해야 한다.

# 출력된 데이터는 지정된 순서(오름차순 또는 내림차순)를 따라야 하며, 역순인 요소가 없어야 한다.

# 출력은 입력 데이터의 순서만 바꾼 재배열이어야 한다 (원소의 추가나 삭제가 없어야 한다).

3. 분류

정렬 알고리즘은 다양한 기준에 따라 분류될 수 있다. 주요 분류 기준은 다음과 같다.

'''계산 복잡도''': 리스트 크기 ''n''에 따른 알고리즘의 성능을 O 표기법으로 나타낸다. 최선, 최악, 평균 실행 시간으로 평가하며, 원소들의 교환 횟수도 고려될 수 있다.
'''메모리 사용량''': 정렬 과정에서 필요한 추가적인 메모리 공간의 크기. 특히, 정렬 대상이 저장된 공간 외에 거의 추가 메모리를 사용하지 않는 제자리 정렬(in-place sort) 방식이 있다. 엄밀히는 O(1) 추가 메모리를 의미하지만, O(log ''n'')까지 제자리 정렬로 간주하기도 한다.^[46]^[47]^[48] 데이터 크기가 커서 주기억장치에 모두 올릴 수 없을 때는 보조 기억 장치를 활용하는 외부 정렬 방식이 사용된다.
'''재귀''': 알고리즘 구현 방식이 재귀적인지, 반복적인지, 또는 둘 다 가능한지에 따른 분류이다. 예를 들어 병합 정렬은 재귀적으로 구현될 수도 있고, 반복적으로 구현될 수도 있다.
'''안정성''': 안정 정렬 알고리즘은 값이 동일한 요소(키)들의 상대적인 순서가 정렬 후에도 입력 순서와 동일하게 유지된다.
'''비교 정렬 여부''': 비교 정렬은 요소들 간의 비교 연산만을 통해 순서를 결정하는 방식이다. 비교를 사용하지 않는 방식(예: 계수 정렬, 기수 정렬)도 있다.
'''일반적인 방식''': 알고리즘의 핵심적인 작동 원리에 따른 분류이다. 삽입, 교환(버블 정렬, 퀵 정렬 등), 선택(힙 정렬 등), 병합 등의 방식이 있다.
'''직렬/병렬''': 알고리즘이 단일 프로세서에서 순차적으로 실행되는 직렬 알고리즘인지, 여러 프로세서를 활용하여 동시에 처리하는 병렬 알고리즘인지에 따른 분류이다. 대부분의 기본적인 설명은 직렬 알고리즘을 가정한다.
'''적응성''': 입력 데이터가 이미 어느 정도 정렬되어 있는 경우, 이를 활용하여 더 빠르게 동작하는지 여부이다. 이러한 특징을 가진 알고리즘을 적응 정렬(adaptive sort)이라고 한다.
'''온라인''': 삽입 정렬과 같이 데이터가 순차적으로 입력되는 스트림 환경에서도 정렬을 수행할 수 있는지 여부이다.

3. 1. 안정성

안정 정렬의 예시. 카드를 안정 정렬로 정렬할 때, 두 개의 5는 정렬된 출력에서도 원래와 같은 순서로 유지되어야 한다. 불안정 정렬로 정렬할 때는 정렬된 출력에서 5의 순서가 반대로 바뀔 수 있다.

안정 정렬(Stable sort) 알고리즘은 정렬 과정에서 값이 동일한 요소들의 상대적인 순서가 입력 순서와 동일하게 유지되도록 하는 정렬 방식이다. 예를 들어, 오른쪽 그림과 같이 플레잉 카드를 숫자(랭크)를 기준으로 정렬한다고 가정해 보자. 이때 무늬는 고려하지 않는다. 안정 정렬 알고리즘을 사용하면, 원래 카드 덱에서 앞에 있던 '다이아몬드 5'가 뒤에 있던 '하트 5'보다 정렬된 결과에서도 항상 앞에 위치하게 된다. 반면, 불안정 정렬 알고리즘을 사용하면 두 '5' 카드의 순서가 바뀔 수도 있다.

안정성은 특정 상황에서 매우 중요하다. 예를 들어, 학생 명단을 먼저 이름순으로 정렬한 뒤, 다시 반별로 정렬한다고 생각해 보자. 만약 반별 정렬에 안정 정렬 알고리즘을 사용한다면, 같은 반 학생들 사이에서는 이전에 정렬된 이름 순서가 그대로 유지된다. 하지만 불안정 정렬을 사용하면 같은 반 학생들의 이름 순서가 뒤섞여 원래 의도했던 정렬 결과를 얻기 어려울 수 있다.

더 형식적으로 설명하면, 정렬 대상이 되는 데이터는 여러 정보(값)로 이루어진 레코드 또는 튜플로 볼 수 있다. 이때 정렬의 기준이 되는 특정 값을 키(key)라고 부른다. 카드 예시에서 각 카드는 (랭크, 무늬)라는 레코드로 표현될 수 있으며, 여기서 키는 '랭크'이다. 어떤 정렬 알고리즘이 두 레코드 R과 S의 키 값이 같을 때, 원래 목록에서 R이 S보다 앞에 있었다면 정렬된 목록에서도 항상 R이 S보다 앞에 오도록 보장할 경우, 이 알고리즘을 안정적이라고 한다.

하지만 모든 경우에 안정성이 중요한 것은 아니다. 예를 들어, 정수 배열처럼 값이 같은 요소들을 서로 구별할 수 없거나, 데이터 전체가 하나의 키로 취급되는 경우에는 안정성이 문제되지 않는다. 또한, 모든 요소의 키 값이 서로 다르다면 안정성은 고려할 필요가 없다.

불안정 정렬 알고리즘도 특별한 방법을 통해 안정적으로 만들 수 있다. 한 가지 방법은 키 값을 비교할 때, 키 값이 동일한 경우에는 원래 입력 목록에서의 순서를 추가적인 비교 기준으로 사용하는 것이다. 하지만 이 방법은 원래 순서를 기억하기 위한 추가적인 메모리 공간과 처리 시간이 필요할 수 있다.

안정 정렬을 이용한 카드 정렬 예시. 먼저 랭크별로 정렬한 뒤, 무늬별로 안정 정렬을 수행하면 각 무늬 내에서 랭크 순서가 유지된다.

안정 정렬은 여러 개의 키를 기준으로 데이터를 정렬할 때 유용하게 사용된다. 예를 들어, 카드 한 벌을 먼저 무늬(클럽 ♣, 다이아몬드 ♦, 하트 ♥, 스페이드 ♠ 순서)별로 정렬하고, 각 무늬 안에서는 카드 숫자(랭크) 순서대로 정렬하고 싶다고 가정해 보자. 이 작업은 먼저 카드를 랭크 기준으로 정렬한 다음(이때는 어떤 정렬 알고리즘을 사용해도 무방하다), 그 결과를 무늬 기준으로 안정 정렬하면 된다. 안정 정렬을 사용했기 때문에, 두 번째 정렬 단계(무늬별 정렬)에서 같은 무늬 카드들의 상대적인 순서, 즉 이전에 정렬된 랭크 순서가 그대로 유지된다. 이러한 아이디어는 여러 개의 키를 사용하는 정렬 방식, 예를 들어 기수 정렬(Radix sort) 등에서 활용된다. 물론, 불안정 정렬을 사용하더라도 처음부터 키 비교 방식을 '무늬 우선, 무늬가 같으면 랭크 비교'와 같이 복합적으로 설계하면 동일한 결과를 얻을 수도 있다.

3. 2. 계산량

입력되는 리스트의 항목 수 ''n''에 기초한 계산량에 따라 정렬 알고리즘을 분류할 수 있다. 전형적인 정렬 알고리즘의 성능은 O 표기법을 사용하여 나타내며, 최선의 경우, 평균적인 경우, 최악의 경우로 나누어 평가한다.

일반적인 직렬 정렬 알고리즘의 경우, 좋은 성능은 O(''n'' log ''n'')이며, 나쁜 성능은 O(''n''²)이다. 직렬 정렬의 이상적인 성능은 O(''n'')이지만, 비교를 기반으로 하는 정렬에서는 평균적으로 달성하기 어렵다. 병렬 정렬의 경우 O(log² ''n'') 또는 최적으로 O(log ''n'')의 성능을 목표로 한다.

비교 정렬은 두 항목을 비교하는 연산을 통해 순서를 결정하는 방식으로, 일반적인(무작위로 정렬된) 데이터 정렬에 대해 적어도 Ω(

n \log n

)의 비교 횟수가 필요하다는 이론적 한계가 있다. 이는 어떤 비교 정렬 알고리즘이라도 특정 입력에 대해서는 점근적으로

n \log n

회의 비교가 필요함을 의미한다.

=== 비교 정렬 알고리즘의 성능 ===

다음 표는 배열에 저장된 ''n''개의 데이터를 정렬하는 비교 정렬 알고리즘들의 성능을 나타낸다. 계산 시간 표기에 사용되는 기호 O(오)는 란다우 표기법을 참조하라. 평균 실행 시간과 최악 실행 시간은 시간 복잡도를 나타내며, 정렬 키의 길이는 일정하고 비교나 교환 같은 연산은 상수 시간에 수행된다고 가정한다. 메모리 사용량은 입력 데이터 저장 영역 외에 추가로 필요한 공간을 의미한다.

명칭	평균 계산 시간	최악 계산 시간	메모리 사용량	안정성	방법	비고
버블 정렬	$O(n^2)$	$O(n^2)$	$O(1)$	안정	교환
셰이커 정렬	$O(n^2)$	$O(n^2)$	$O(1)$	안정	교환
콤 정렬	$O(n \log n)$	$O(n^2)$	$O(1)$	불안정	교환	코드 크기가 작아도 된다.
놈 정렬	$O(n^2)$	$O(n^2)$	$O(1)$	안정	교환
선택 정렬	$O(n^2)$	$O(n^2)$	$O(1)$	불안정	선택	안정 정렬로도 구현 가능
삽입 정렬	$O(n^2)$	$O(n^2)$	$O(1)$	안정	삽입	최선 계산 시간이 $\Theta(n)$ 이 된다.
셸 정렬	$O(n \log n)$	≧ $O(n^{1.5})$	$O(1)$	불안정	삽입	최악 $\Omega(n^\frac{3}{2})$ 이나 $\Omega(n^\frac{4}{3})$ 의 수열이 실용화되고 있다.
트리 정렬	$O(n \log n)$	$O(n \log n)$	$O(n)$	안정	삽입	균형 이진 탐색 트리를 사용한 경우
도서관 정렬	$O(n \log n)$	$O(n^2)$	$O(n)$	안정	삽입
병합 정렬	$O(n \log n)$	$O(n \log n)$	$O(n)$	안정	병합	연결 리스트의 경우 $O(1)$ 외부 메모리.
In-place 병합 정렬	$O(n \log^2 n)$	$O(n \log^2 n)$	$O(1)$	안정	병합	[https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8633 구현 예시]
힙 정렬	$O(n \log n)$	$O(n \log n)$	$O(1)$	불안정	선택
스무스 정렬	—	$O(n \log n)$	$O(1)$	불안정	선택
퀵 정렬	$O(n \log n)$	$O(n^2)$	$O(\log n)$	불안정	분할	메모리는 콜 스택 (단순한 구현에서는 $\Omega(n)$ 이 된다)
인트로 정렬	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	불안정	혼성	메모리는 콜 스택
인내 정렬	—	$O(n^2)$	$O(n)$	불안정	삽입	$O(n \log n)$ 이내에 모든 최장 증가 부분열을 찾는다.
스트랜드 정렬	$O(n \log n)$	$O(n^2)$	$O(n)$	안정	선택
짝수-홀수 정렬	$O(n^2)$	$O(n^2)$	$O(1)$	안정	교환
셰어 정렬	$O(n^{1.5})$	$O(n^{1.5})$	$O(1)$	불안정	교환

=== 비-비교 정렬 알고리즘의 성능 ===

다음 표는 비교 연산 외의 방법(예: 키 값의 분포나 자릿수 이용)을 사용하는 정렬 알고리즘의 목록이다. 이 알고리즘들은 비교 정렬의 하한인 O(''n'' log ''n'')보다 더 나은 성능을 보일 수 있다. ''k''는 키의 길이, ''s''는 구현에 사용되는 청크의 크기를 나타낸다. 일부 알고리즘은 키가 충분히 길고 중복되지 않는다는 가정(즉, ''n'' << 2^''k'') 하에 최적의 성능을 보인다.

명칭	평균 계산 시간	최악 계산 시간	메모리 사용량	안정성	n << 2^k?	비고
비둘기집 정렬	$O(n+2^k)$	$O(n+2^k)$	$O(2^k)$	안정	○
버킷 정렬	$O(n+k)$	$O(n^2)$	$O(nk)$	안정	×	입력 데이터는 정의역에 균일하게 분포한다고 가정
계수 정렬	$O(n+2^k)$	$O(n+2^k)$	$O(n+2^k)$	안정	○
LSD 기수 정렬	$O(nk/s)$	$O(nk/s)$	$O(n)$	안정	×
MSD 기수 정렬	$O(nk/s)$	$O(n(k/s)2^s)$	$O((k/s)2^s)$	불안정	×
스프레드 정렬	$O(nk/\log n)$	$O(n(k-\log n)^{0.5})$	$O(n)$	불안정	×	n << 2^k의 경우의 계산 시간이지만, 그 외의 경우에도 정렬 가능
플래시 정렬	$O(n)$ ?	N/A	$O(n)$ ?	안정	×

=== 비실용적이거나 특수한 정렬 알고리즘 ===

다음 표는 성능이 매우 나빠 일반적인 상황에서는 사용되지 않거나, 특수한 하드웨어 또는 가정이 필요한 정렬 알고리즘의 목록이다.

명칭	평균 계산 시간	최악 계산 시간	메모리 사용량	안정성	크기 비교	비고
보고 정렬	$O(n \cdot n!)$	∞	$O(1)$	불안정	○	평균 시간은 크누스의 셔플을 사용한 경우
보조 정렬 (보고 정렬 변형)	$O(n \cdot n!)$	∞	$O(1)$	불안정	○	평균 시간은 보고 정렬의 약 절반에 점근한다.
스투지 정렬	$O(n^{2.71})$	$O(n^{2.71})$	$O(\log n)$	불안정	○
수면 정렬	값의 최댓값 × 프로세스 기동 단위 시간 (실제로는 오차 있음)	동일	$O(n)$ ?	불안정	?	조건이 특수하다. 실용적인 정확성이 보증되지 않는다.
구슬 정렬	N/A	N/A	—	N/A	×	전용 하드웨어가 필요
단순 팬케이크 정렬	$O(n)$	$O(n)$	$O(\log n)$	불안정	○	반전을 상수 시간에 행할 수 있다고 가정
소팅 네트워크	$O(\log n)$	$O(\log n)$	$O(n \log n)$	안정	×	크기 $O(n \log n)$ 의 회로가 필요.
비트닉 정렬	$O(\log^2 n)$	$O(\log^2 n)$	$O(n \log^2 n)$	불안정	×	계산 시간과 메모리 사용량은 소팅 네트워크로 구현했을 때의 값
배처 기수 병합 정렬	$O(\log^2 n)$	$O(\log^2 n)$	$O(n \log^2 n)$	불안정	×	계산 시간과 메모리 사용량은 소팅 네트워크로 구현했을 때의 값

=== 비교 정렬 알고리즘의 최악 계산량 하한 ===

정렬을 수행할 때, 요소 간의 순서 결정이 두 요소의 크기 비교 처리만을 사용하여 이루어진다고 가정하면, $n$ 개의 요소로 구성된 리스트를 정렬하는 알고리즘의 최악 비교 횟수는 $\Omega(n \log n)$ 회가 된다. 즉, 어떤 비교 정렬 알고리즘이라도 입력에 따라서는 점근적으로 $n \log n$ 회의 비교가 필요하게 된다.

이 이유는 다음과 같이 설명될 수 있다. 비교 정렬 알고리즘의 처리 과정을 이진 결정 트리로 나타낼 수 있다. 각 내부 노드는 두 요소의 비교를 나타내고, 두 개의 가지는 비교 결과에 따른 다음 단계를 나타낸다. 잎 노드는 정렬이 완료된 상태를 나타낸다. 트리의 높이는 최악의 경우 비교 횟수에 해당한다.

$n$ 개의 요소로 이루어진 리스트의 가능한 모든 순서(순열)는 $n!$ 가지이다. 올바른 정렬 알고리즘은 이 $n!$ 가지의 서로 다른 입력 순서 각각에 대해 유일한 정렬 결과를 출력해야 하므로, 결정 트리의 잎 노드는 최소 $n!$ 개 이상이어야 한다. 높이가 $m$ 인 이진 트리의 잎 노드 수는 최대 $2^m$ 개이므로, $n! \leq 2^m$ 이라는 관계가 성립한다.

스털링 근사에 의해 $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$ 이고, $\left(\frac{n}{e}\right)^n < n!$ 이므로, $\left(\frac{n}{e}\right)^n < 2^m$ 이다. 양변에 로그를 취하면 $m > \log_2 \left(\frac{n}{e}\right)^n = n(\log_2 n - \log_2 e)$ 이다. 따라서, 트리의 높이 $m$ 은 $\Omega(n \log n)$ 이 된다.

결론적으로, 임의의 비교 정렬 알고리즘의 최악 계산량은 $\Omega(n \log n)$ 이며, 이는 비교 정렬 알고리즘의 최악 계산량의 이론적인 하한이 점근적으로 $n \log n$ 임을 의미한다. 병합 정렬, 힙 정렬 등 최악 계산량이 $O(n \log n)$ 인 비교 정렬 알고리즘들은 이 하한에 도달하므로 점근적으로 최적이라고 할 수 있다.

3. 3. 내부 정렬과 외부 정렬

정렬 알고리즘은 사용하는 메모리의 양과 위치에 따라 내부 정렬과 외부 정렬로 나눌 수 있다.

'''내부 정렬'''(Internal sort)은 정렬할 모든 데이터가 주기억장치(RAM)에 올라와 처리되는 방식이다. 데이터가 저장된 원래의 메모리 공간 내에서 추가적인 공간을 거의 사용하지 않고 정렬하는 제자리 정렬(in-place sort)과 관련이 깊으며, 정렬할 데이터 자체를 저장하는 공간 외에 추가적으로 아주 적은 양의 메모리(O(1) 또는 O(log ''n''))만을 사용한다. 예를 들어 퀵 정렬처럼 재귀 호출을 사용하는 알고리즘은 호출 스택을 위해 O(log ''n'')의 추가 공간이 필요하지만, 일반적으로 내부 정렬로 분류된다.

'''외부 정렬'''(External sort)은 정렬할 데이터의 양이 너무 많아서 주기억장치에 모두 수용할 수 없을 때 사용된다. 이때는 하드 디스크나 SSD와 같은 보조 기억 장치를 활용하여 정렬을 수행한다. 외부 정렬은 데이터를 처리하기 위해 주기억장치 외부에 O(''n'') 이상의 임시 저장 공간을 필요로 한다.

외부 정렬은 정렬 대상 배열이 주기억장치 용량을 초과할 때 필수적이다. 이 경우, 알고리즘의 효율성은 단순히 데이터 비교 횟수보다 보조 기억 장치와의 데이터 입출력(읽기/쓰기) 횟수에 더 크게 좌우된다. 가상 메모리 스왑(swap) 발생을 줄이고, 데이터 접근의 참조 지역성을 높이는 것이 중요해진다. 예를 들어 퀵 정렬은 주기억장치 내에서는 매우 효율적이지만, 데이터가 너무 커서 보조 기억 장치를 사용해야 하는 상황에서는 잦은 스왑으로 인해 성능이 크게 저하될 수 있다.

이러한 문제를 해결하기 위해 외부 정렬에서는 다음과 같은 기법들이 사용된다.

'''태그 정렬'''(Tag sort): 실제 데이터(관계형 데이터베이스의 레코드 등) 대신 크기가 작은 인덱스나 키 값만을 먼저 정렬하는 방식이다. 인덱스를 정렬하면 원래 데이터의 정렬 순서를 알 수 있으며, 인덱스 자체가 작기 때문에 메모리에 더 많이 올릴 수 있어 스왑 문제를 줄일 수 있다.^[44]
'''알고리즘 조합''': 데이터를 여러 개의 작은 덩어리(chunk)로 나누어 각각 주기억장치에서 효율적으로 작동하는 내부 정렬 알고리즘(예: 퀵 정렬, 힙 정렬)으로 정렬한 뒤, 이 정렬된 덩어리들을 병합 정렬과 유사한 방식으로 합쳐 전체 데이터를 정렬하는 방법이다.

이론적으로는 모든 내부 정렬 알고리즘은 인덱스를 생성하여 처리하는 방식으로 외부 정렬처럼 만들 수 있지만, 일반적으로는 각 방식의 특성에 맞는 알고리즘을 사용하는 것이 효율적이다.

3. 4. 비교 정렬

개별 항목을 비교 연산으로 크고 작음을 판정하는 것을 기본으로 하는 정렬을 비교 정렬이라고 한다. 예를 들어 거품 정렬(bubble sort)은 비교하는 원소들이 숫자거나, 문자열이거나, 심지어는 복잡한 객체에 대해서도 순서가 결정되어 있다면 적용할 수 있다.

다음은 비교 정렬 알고리즘들의 성능을 요약한 표이다. 비교 정렬은 최악의 경우

\Omega(n \log n)

보다 더 나은 성능을 낼 수 없다.^[49]

비교 정렬
이름	최선	평균	최악	메모리	안정성	방식
퀵 정렬	$n \log n$ (변형 시 $n$ )	$n \log n$	$n^2$	평균 $\log n$ , 최악 $n$	아니오 (안정판 존재)	파티셔닝
합병 정렬	$n \log n$	$n \log n$	$n \log n$	$n$	예	합병
제자리 합병 정렬	—	—	$n \log^2 n$ (하이브리드의 경우 $n \log n$ )	1	예	합병
힙 정렬	$n$ (모든 키가 구별되면 $n \log n$ )	$n \log n$	$n \log n$	1	아니오	선택
삽입 정렬	$n$	$n^2$	$n^2$	1	예	삽입
인트로소트	$n \log n$	$n \log n$	$n \log n$	$\log n$	아니오	파티셔닝, 선택
선택 정렬	$n^2$	$n^2$	$n^2$	1	아니오	선택
팀소트	$n$	$n \log n$	$n \log n$	$n$	예	삽입, 합병
큐브소트	$n$	$n \log n$	$n \log n$	$n$	예	삽입
셸 정렬	$n \log n$	간격 순서에 따라 다름	간격 순서에 따라 다름 (최선은 $n^{1.25}$ )	1	아니오	삽입
거품 정렬	$n$	$n^2$	$n^2$	1	예	교환
이진 트리 정렬	$n \log n$	$n \log n$	$n \log n$ (균형 트리)	$n$	예	삽입
사이클 정렬	$n^2$	$n^2$	$n^2$	1	아니오	삽입
라이브러리 소트	$n$	$n \log n$	$n^2$	$n$	예	삽입
페이션스 소팅	$n$	—	$n \log n$	$n$	아니오	삽입, 선택
스무스소트	$n$	$n \log n$	$n \log n$	1	아니오	선택
스트랜드 소트	$n$	$n^2$	$n^2$	$n$	예	선택
토너먼트 정렬	$n \log n$	$n \log n$	$n \log n$	$n$ ^[50]	아니오	선택
칵테일 정렬	$n$	$n^2$	$n^2$	1	예	교환
빗질 정렬	$n \log n$	$n^2$	$n^2$	1	아니오	교환
그놈 정렬	$n$	$n^2$	$n^2$	1	예	교환
언셔플 소트^[51]	$n$	$kn$	$kn$	연결 리스트는 제자리, 배열은 추가 공간 필요	아니오	분산, 합병
Franceschini's method^[52]	—	$n \log n$	$n \log n$	1	예	?
블록 정렬	$n$	$n \log n$	$n \log n$	1	예	삽입, 합병
홀짝 정렬	$n$	$n^2$	$n^2$	1	예	교환
커브 정렬	$n$	$n^2$	$n^2$	$\Omega(1) \cap \mathcal{O}(n)$	예	삽입, 계수

비교 정렬 알고리즘들은 아무리 빨라도 최악의 경우 $\Omega(n \log n)$ 시간을 필요로 한다. 이는 비교 정렬 알고리즘을 결정 트리 형태로 나타낼 수 있다는 점에서 증명할 수 있다. $n$ 개의 원소들의 가능한 모든 순열은 $n!$ 가지인데, 이 모든 경우의 수를 구분하여 정렬 결과를 내려면 결정 트리의 깊이(비교 횟수)가 최소한 $\lceil \log_2 n! \rceil$ 이 되어야 한다. 스털링 근사에 따르면 $\log_2 n!$ 은 대략 $n \log_2 n$ 에 비례하므로, 비교 정렬의 시간 복잡도 하한은 $\Omega(n \log n)$ 이 된다.

따라서 합병 정렬, 힙 정렬과 같이 최악의 경우에도 $O(n \log n)$ 의 시간 복잡도를 가지는 비교 정렬 알고리즘들은 점근적으로 최적의 성능을 가진다고 할 수 있다.

비교 정렬이 아닌 알고리즘(예: 기수 정렬)들은 이러한 $\Omega(n \log n)$ 시간 복잡도 제약이 없지만, 대신 입력 데이터의 형태에 제약을 받는 경우가 많다. 예를 들어 기수 정렬은 숫자나 문자열처럼 특정 기준에 따라 쉽게 분리될 수 있는 데이터에는 매우 효율적이지만, 일반적인 객체 비교에는 비교 정렬보다 느릴 수 있다.

4. 알고리즘의 비교

컴퓨터 과학 분야에서 정렬 알고리즘은 기본적인 문제이지만 효율적인 해결을 위해 오랫동안 연구되어 왔다. 에니악과 유니박 개발에 참여했던 베티 홀버튼과 같은 초기 연구자들부터 시작하여^[46]^[47], 2000년대에 개발된 팀소트나 라이브러리 소트와 같이 현재도 새로운 알고리즘들이 개발되고 있다.^[48]

다양한 정렬 알고리즘들은 여러 기준에 따라 성능과 특징을 비교하여 평가할 수 있다. 알고리즘을 선택할 때는 주어진 데이터의 특성과 요구 사항에 가장 적합한 것을 고르는 것이 중요하다. 주요 비교 기준은 다음과 같다.

시간 복잡도: 알고리즘이 데이터를 정렬하는 데 걸리는 시간을 데이터 크기 ''n''에 대한 함수로 나타낸다. 최선, 평균, 최악의 경우로 나누어 평가하며, 점근 표기법 (예: O(''n'' log ''n''), O(''n''²))을 사용하여 표현한다. 비교 정렬의 경우 이론적으로 Ω(''n'' log ''n'')보다 빠른 평균 시간 복잡도를 가질 수 없다.
메모리 사용량: 정렬 과정에서 입력 데이터 외에 추가적으로 필요한 메모리 공간의 양을 의미한다. 추가 메모리를 거의 사용하지 않는 알고리즘을 제자리 정렬(in-place sort)이라고 하며, 보통 O(1) 또는 O(log ''n'')의 추가 공간을 사용하는 경우를 말한다.
안정성: 값이 같은 원소들의 상대적인 순서가 정렬 후에도 유지되는지 여부를 나타낸다. 안정 정렬은 여러 기준으로 데이터를 순차적으로 정렬할 때 유용하다.
비교 정렬 여부: 원소 간의 대소 비교 연산만을 통해 정렬하는지, 아니면 다른 정보(예: 값의 분포나 자릿수)를 활용하는지에 따라 구분된다. 계수 정렬이나 기수 정렬 등은 비교 정렬이 아니다.
구현 방식: 삽입, 교환, 선택, 병합 등 알고리즘의 기본적인 작동 원리에 따라 분류할 수 있다.
기타: 재귀 사용 여부, 입력 데이터의 정렬 상태에 따른 성능 변화(적응성) 등도 비교 기준이 될 수 있다.

이러한 기준들을 바탕으로 각 정렬 알고리즘의 장단점을 파악하고, 특정 응용 환경에 가장 적합한 알고리즘을 선택하는 것이 중요하다. 예를 들어, 데이터 크기가 작을 때는 구현이 간단한 알고리즘이 유리할 수 있고, 메모리 사용량이 매우 제한적일 때는 제자리 정렬이 필요하며, 정렬 후에도 원래 순서 유지가 중요할 때는 안정 정렬을 선택해야 한다.

4. 1. 비교 정렬

비교 정렬은 원소들을 정렬할 때 원소들의 순서(크고 작음)에만 의존하여 정렬하는 알고리즘들을 일컫는다.^[49] 예를 들어 거품 정렬은 비교하는 원소들이 숫자거나, 문자열이거나, 심지어는 복잡한 객체라도 순서가 결정되어 있다면 적용할 수 있다.

비교 정렬 알고리즘들은 아무리 빨라도 평균적으로

\Omega(n \log n)

의 시간 복잡도가 필요하다.^[4] 이는 비교 정렬 과정을 결정 트리 형태로 나타낼 수 있기 때문에 증명 가능하다.

n

개의 원소로 만들 수 있는 순열은 총

n!

가지인데, 이 모든 경우의 수를 잎 노드로 가지는 결정 트리의 최소 깊이는 스털링 근사에 따라

\lceil \log_2 n! \rceil \approx n \log_2 n

이기 때문이다. 따라서 어떤 비교 정렬 알고리즘이라도 최악의 경우에는 점근적으로

n \log n

번의 비교 연산이 필요하다.

병합 정렬, 힙 정렬 등은 최악의 경우에도

O(n \log n)

의 시간 복잡도를 가지므로, 점근적으로 최적의 성능을 내는 비교 정렬 알고리즘이라고 할 수 있다.

비교 정렬이 아닌 알고리즘(예: 기수 정렬, 계수 정렬)은 이러한 시간 복잡도 하한의 제약을 받지 않지만, 적용 가능한 데이터 유형에 제약이 있을 수 있다. 예를 들어 기수 정렬은 사전순으로 표기하고 분리하기 쉬운 숫자나 문자열에는 효과적이지만, 그렇지 않은 객체에는 일반 비교 정렬보다 느릴 수 있다.

=== 안정성 ===

'''안정 정렬'''(Stable sort) 알고리즘은 정렬 과정에서 값이 같은 원소들의 상대적인 순서가 유지되는 정렬 방식을 말한다. 예를 들어, (랭크, 무늬)로 구성된 카드 덱을 랭크(숫자) 기준으로 정렬할 때, 안정 정렬은 값이 같은 카드(예: 여러 개의 5 카드)들의 초기 순서를 그대로 유지한다. 만약 입력에서 하트 5가 다이아몬드 5보다 앞에 있었다면, 안정 정렬 후에도 하트 5는 다이아몬드 5보다 앞에 위치한다. 불안정 정렬의 경우 이 순서가 바뀔 수도 있다.

안정성은 동일한 데이터 집합을 여러 기준에 따라 순차적으로 정렬할 때 중요하다. 예를 들어, 학생 명단을 먼저 이름순으로 정렬한 후, 다시 반 순서로 정렬한다고 가정해보자. 이때 반 순서로 정렬할 때 안정 정렬 알고리즘을 사용하면, 같은 반 학생들 사이에서는 이전에 정렬된 이름 순서가 그대로 유지된다. 만약 불안정 정렬을 사용하면, 반별 정렬 과정에서 이름 순서가 뒤섞일 수 있다.

정수와 같이 동일한 값을 가진 요소들을 구별할 수 없거나, 데이터 전체가 정렬 키(key)로 사용되는 경우에는 안정성이 문제되지 않는다. 또한 모든 키 값이 고유하다면 안정성은 고려할 필요가 없다.

불안정 정렬 알고리즘도 안정적으로 구현할 수 있다. 한 가지 방법은 정렬 키 비교 시, 키 값이 같을 경우 원래 입력 순서를 추가적인 비교 기준으로 사용하는 것이다. 하지만 이를 위해서는 원래 순서를 기억하기 위한 추가적인 메모리 공간과 시간이 필요할 수 있다.

=== 비교 정렬 알고리즘 목록 ===

다음 표는 다양한 비교 정렬 알고리즘의 성능 특성을 요약한 것이다. ''n''은 정렬할 항목의 수를 나타낸다. 시간 복잡도는 빅 오 표기법으로 표시되며, 로그의 밑은 중요하지 않다. 메모리 사용량은 입력 데이터 자체를 제외한 추가적인 공간 요구량을 의미한다.

비교 정렬 알고리즘 비교
이름	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	메모리 사용량	안정성	방식	비고
퀵 정렬	$O(n \log n)$ (변형 시 $O(n)$ )	$O(n \log n)$	$O(n^2)$	$O(\log n)$ 평균, 최악 $O(n)$	아니오 (안정 버전 존재)	분할	일반적으로 $O(\log n)$ 스택 공간으로 제자리 정렬 수행 가능.^[9]^[10]
합병 정렬	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	예	병합	병렬 처리 유리.^[6] 연결 리스트의 경우 $O(1)$ 외부 메모리.
제자리 합병 정렬	—	$O(n \log^2 n)$	$O(n \log^2 n)$ (하이브리드 시 $O(n \log n)$ )	$O(1)$	예	병합	안정적인 제자리 병합 가능.^[5]
힙 정렬	$O(n \log n)$ (모든 키가 다를 때)	$O(n \log n)$	$O(n \log n)$	$O(1)$	아니오	선택
삽입 정렬	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	예	삽입	거의 정렬된 데이터에 효율적. 역순 요소 d개일 때 최악 $O(n + d)$ .
인트로 정렬	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(\log n)$	아니오	분할, 선택 (힙)	C++ STL 등에서 사용됨.
선택 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	아니오	선택	안정적으로 구현 가능 (추가 공간 필요).^[11]
팀 정렬	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	예	삽입, 병합	파이썬, 자바, 안드로이드 등에서 사용. 실제 데이터에서 좋은 성능. 데이터가 이미 정렬되었거나 역순으로 정렬된 경우 n-1번의 비교를 수행.
큐브 정렬	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	예	삽입	데이터가 이미 정렬되었거나 역순으로 정렬된 경우 n-1번의 비교를 수행.
셸 정렬	$O(n \log n)$	간격(gap) 순서에 따라 다름 (예: $O(n^{4/3})$ )	간격 순서에 따라 다름 (예: $O(n^{3/2})$ , 최선 알려진 것: $O(n \log^2 n)$ )	$O(1)$	아니오	삽입	구현이 간단. 작은 코드 크기.
거품 정렬	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	예	교환	교육용 외 실제 사용 드묾. 매우 작은 코드 크기.
트리 정렬	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$ (균형 트리) $O(n^2)$ (불균형 트리)	$O(n)$	예	삽입	균형 이진 탐색 트리 사용 시 효율적.
사이클 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	아니오	선택 (삽입)	쓰기 연산 횟수를 이론적으로 최적화.
라이브러리 정렬	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(n)$	아니오	삽입	간격을 둔 삽입 정렬. 높은 확률 시간 범위를 보장하기 위해 입력을 임의로 순열해야 하므로 안정적이지 않음.
인내 정렬	$O(n)$ (거의 정렬 시)	$O(n \log n)$	$O(n \log n)$	$O(n)$	아니오	삽입, 선택	$O(n \log n)$ 에서 모든 최장 증가 부분 수열을 찾음.
스무스 정렬	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	아니오	선택 (힙 변형)	힙 정렬의 적응형 버전. 레오나르도 수 기반 힙 사용.
스트랜드 정렬	$O(n)$	$O(n^2)$	$O(n^2)$	$O(n)$	예	선택
토너먼트 정렬	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$ ^[7]^[50]	아니오	선택	힙 정렬의 변형.
칵테일 셰이커 정렬	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	예	교환	거품 정렬의 양방향 버전. 목록 끝에 있는 작은 값을 잘 처리.
빗질 정렬	$O(n \log n)$	$O(n^2)$	$O(n^2)$	$O(1)$	아니오	교환	거품 정렬보다 평균적으로 빠름.
그놈 정렬	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	예	교환 (삽입과 유사)	구현이 매우 간단. 매우 작은 코드 크기.
블록 정렬	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	예	삽입, 병합	안정적인 제자리 정렬. 블록 기반 $O(n)$ 제자리 병합 알고리즘과 바닥-위 병합 정렬 결합.^[8]
짝홀 정렬	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	예	교환	병렬 처리에 용이.

=== 실제 사용 ===

실제 응용 프로그램에서는 특정 상황에 맞는 정렬 알고리즘이 선택된다. 작은 데이터 집합에는 삽입 정렬처럼 구현이 간단하고 상수 요인이 작은 알고리즘이 효율적일 수 있다. 반면 큰 데이터 집합에는 점근적으로 효율적인 힙 정렬, 합병 정렬, 퀵 정렬 등이 주로 사용된다.

많은 경우, 실제 라이브러리 구현에서는 하이브리드 알고리즘을 사용한다. 예를 들어, 전체적으로는 퀵 정렬이나 합병 정렬을 사용하다가 데이터 크기가 일정 수준 이하로 작아지면 삽입 정렬로 전환하는 방식이다. 팀소트(Timsort)는 합병 정렬과 삽입 정렬을 결합하고 데이터의 기존 정렬 상태를 활용하는 방식으로, 파이썬, 자바, 안드로이드 등에서 표준 정렬 알고리즘으로 채택되었다. 인트로소트(Introsort)는 퀵 정렬을 기반으로 하되 최악의 경우 힙 정렬로 전환하여 $O(n \log n)$ 성능을 보장하며, 일부 C++ 표준 라이브러리 및 .NET 등에서 사용된다.

물리적으로 객체를 정렬할 때(예: 종이, 시험지, 책 등을 알파벳순으로 정렬) 사람들은 직관적으로 작은 집합에는 삽입 정렬을 사용하는 경향이 있다. 더 큰 집합의 경우, 초기 문자 등으로 버킷을 나누어 정렬하는 방식을 사용하기도 한다. 물리적 정렬에서는 공간은 비교적 여유롭지만(예: 바닥에 펼쳐놓기), 객체를 옮기는 연산, 특히 먼 거리 이동은 비용이 크므로 참조 지역성이 중요하다. 합병 정렬은 두 손을 사용하여 병합할 수 있어 물리적 정렬에도 실용적이지만, 힙 정렬이나 퀵 정렬은 사람이 직접 수행하기에는 부적합하다. 라이브러리 정렬과 같이 공간을 남겨두는 삽입 정렬의 변형도 물리적 정렬에 활용될 수 있다.

4. 2. 비교가 아닌 정렬

정수 정렬 알고리즘과 비교 정렬이 아닌 다른 정렬 알고리즘들은 비교 연산에 기반하지 않으므로, 비교 정렬의 이론적 시간 복잡도 하한선인

\Omega(n \log n)

에 제약을 받지 않는다. 이러한 알고리즘들은 특정 조건 하에서 더 빠른 성능을 보일 수 있다.

아래 표는 주요 비교가 아닌 정렬 알고리즘들의 성능 특성을 요약한 것이다. 표에서 사용된 변수는 다음과 같다.

''n'': 정렬할 항목의 개수
''k'': 키(key)의 크기
''d'': 숫자(digit)의 크기 또는 자릿수
''r'': 정렬될 수의 범위

이 알고리즘 중 다수는 모든 항목이 고유한 키 값을 가질 수 있을 만큼 키의 크기가 충분히 크다는 가정, 즉

n \ll 2^k

(''n''이

2^k

보다 훨씬 작음)을 전제로 한다. 단위 비용 랜덤 접근 기계(Random Access Machine, RAM) 모델에서, 기수 정렬과 같이 실행 시간이

n \cdot \frac{k}{d}

인 알고리즘도 여전히

\Theta(n \log n)

에 비례하는 시간이 소요될 수 있다. 이는 ''n''이

2^\frac{k}{d}

미만으로 제한되고, 정렬 대상 요소가 많아지면 메모리에 저장하기 위해 더 큰 ''k''가 필요하기 때문이다.^[53]^[13]

비교가 아닌 정렬
이름	최선	평균	최악	메모리	안정성	$n \ll 2^k$	비고
비둘기집 정렬	—	$n + 2^k$	$n + 2^k$	$2^k$	예	예	정수가 아닌 데이터는 정렬할 수 없다.
버킷 정렬 (균일 키)	—	$n+k$	$n^2 \cdot k$	$n \cdot k$	예	아니요	입력 데이터가 정렬 범위 내에서 균일하게 분포한다고 가정한다.^[14] 정수가 아닌 데이터는 정렬할 수 없다.
버킷 정렬 (정수 키)	—	$n+r$	$n+r$	$n+r$	예	예	r이 $O(n)$ 일 경우 평균 시간 복잡도는 $O(n)$ 이다.^[15]
계수 정렬	—	$n+r$	$n+r$	$n+r$	예	예	r이 $O(n)$ 일 경우 평균 시간 복잡도는 $O(n)$ 이다.^[14]
LSD 기수 정렬	$n$	$n \cdot \frac{k}{d}$	$n \cdot \frac{k}{d}$	$n + 2^d$	예	아니요	$\frac{k}{d}$ 단계의 재귀 호출이 필요하며, 계수 배열을 위해 $2^d$ 의 메모리가 필요하다.^[14]^[15] 대부분의 분산 정렬과 달리, 정수가 아닌 데이터도 정렬할 수 있다.
MSD 기수 정렬	—	$n \cdot \frac{k}{d}$	$n \cdot \frac{k}{d}$	$n + 2^d$	예	아니요	안정적인 버전은 모든 버킷(bin)을 저장하기 위해 크기 n의 추가 배열을 사용한다. LSD 방식과 마찬가지로 정수가 아닌 데이터도 정렬할 수 있다.
MSD 기수 정렬 (제자리)	—	$n \cdot k$	$n \cdot k$	$2^d$	아니요	아니요	제자리(in-place) 구현의 경우 일반적으로 d=1로 간주하며, $k$ 단계의 재귀 호출이 필요하다. 계수 배열은 사용하지 않거나 매우 작다.
스프레드 정렬(Spreadsort)	n	$n \cdot \frac{k}{d}$	$n \cdot \left( {\frac{k}{s} + d} \right)$	$\frac{k}{d} \cdot 2^d$	아니요	아니요	시간 복잡도 분석은 $n \ll 2^k$ 가정을 기반으로 하지만, 알고리즘 자체는 이 조건 없이도 동작한다. (s는 구현에 사용되는 청크 크기와 관련됨)
버스트 정렬(Burstsort)	—	$n \cdot \frac{k}{d}$	$n \cdot \frac{k}{d}$	$n \cdot \frac{k}{d}$	아니요	아니요	문자열 정렬에서 기수 정렬보다 더 나은 성능을 보일 수 있으며, 입력 문자열의 특성에 영향을 받는다.
플래시 정렬(Flashsort)	n	$n+r$	$n^2$	n	아니요	아니요	선형 시간 성능을 위해서는 입력 데이터가 균일하게 분포해야 한다. 분포가 매우 편향된 경우, 내부적으로 사용하는 정렬(주로 삽입 정렬)의 성능에 따라 최악의 경우 $O(n^2)$ 이 될 수 있다. 제자리 버전은 안정적이지 않다.
우편 배달부 정렬(Postman's sort)	—	$n \cdot \frac{k}{d}$	$n \cdot \frac{k}{d}$	$n+2^d$	—	아니요	버킷 정렬의 변형으로, MSD 기수 정렬과 유사하게 동작한다. 이름처럼 우편 서비스의 요구사항에 특화된 면이 있다.

샘플 정렬(Sample sort)은 데이터를 여러 버킷으로 효율적으로 분배한 뒤, 각 버킷을 병렬적으로 처리하여 정렬하는 방식으로 비교가 아닌 정렬 알고리즘을 병렬화하는 데 사용될 수 있다. 이 방식은 각 버킷이 이미 서로 정렬된 상태이므로 최종적으로 버킷들을 병합할 필요가 없다는 장점이 있다.

4. 3. 기타

일부 정렬 알고리즘들은 앞서 논의된 것들에 비해 속도가 매우 느리다. 예를 들어 보고정렬은 최악의 경우 실행 시간이 무한대에 이를 수 있으며, 꼭두각시 정렬은 O(''n''^{log 3 / log 1.5}) ≈ O(''n''^2.7095...)의 실행 시간을 가진다. 이러한 정렬들은 주로 알고리즘의 실행 시간을 예측하고 분석하는 방법을 설명하기 위한 교육용 예시로 사용된다. 다음 표는 성능이 매우 낮거나 특수한 하드웨어 요구사항 때문에 일반적인 소프트웨어 환경에서는 실용적이지 않은 정렬 알고리즘들을 보여준다.

이름	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	메모리 복잡도	안정성	비교 여부	기타 참고 사항
비드 정렬	n	S	S	n²	예	아니요	양의 정수만 정렬할 수 있다. O(n) 시간에 실행되려면 특수 하드웨어가 필요하다. 소프트웨어 구현 시 실행 시간은 O(S)가 되는데, 여기서 S는 정렬할 모든 정수의 합이다. 작은 정수의 경우 선형 시간으로 간주될 수 있다.
병합 삽입 정렬	n log n (비교 횟수)	n log n (비교 횟수)	n log n (비교 횟수)	다양함	아니요	예	다른 정렬 알고리즘에 비해 최악의 경우 비교 횟수가 매우 적다. 그러나 구현이 복잡하고 데이터 이동이 최적화되지 않아 주로 이론적인 관심 대상이다.
"I Can't Believe It Can Sort"^[16]	n²	n²	n²	1	아니요	예	주로 삽입 정렬 또는 교환 정렬의 잘못된 구현으로 여겨지는 알고리즘이다.
스파게티 정렬	n	n	n	n²	예	투표 방식	일련의 항목을 정렬하기 위한 선형 시간의 아날로그 알고리즘이다. O(n)의 스택 공간이 필요하며 정렬은 안정적이다. n개의 병렬 프로세서가 필요하다. 스파게티 정렬#분석 참조.
정렬 네트워크	다양함	다양함	다양함	다양함	다양함 (안정적인 정렬 네트워크는 더 많은 비교가 필요)	예	비교 순서는 고정된 네트워크 크기를 기반으로 미리 설정된다.
비트닉 정렬	log² n (병렬)	log² n (병렬)	n log² n (비병렬)	1	아니요	예	정렬 네트워크의 한 종류이다.
보고정렬	n	n × n!	무제한	1	아니요	예	임의 섞기 방식으로 작동한다. 예상되는 최선의 경우 실행 시간조차 매우 비효율적이기 때문에 실제 사용보다는 교육적 목적으로 언급된다.^[17] 최악의 경우는 무작위화를 사용할 때 실행 시간이 무한대가 될 수 있지만, 결정론적 버전은 O(n × n!)의 최악 시간 복잡도를 보장한다.
꼭두각시 정렬	n^{log 3 / log 1.5}	n^{log 3 / log 1.5}	n^{log 3 / log 1.5}	n	아니요	예	대부분의 정렬 알고리즘(단순한 것 포함)보다 느리며, 시간 복잡도는 O(n^{log 3 / log 1.5}) ≈ O(n^2.7095...)이다. 안정적으로 만들 수 있으며 정렬 네트워크의 일종이기도 하다.
슬로우소트	n^{Ω(log n)}	n^{Ω(log n)}	n^{Ω(log n)}	n	아니요	예	곱셈과 항복(multiply and surrender) 방식을 사용하는 알고리즘으로, 분할 정복 알고리즘과 대조된다.
프란체스키의 방법^[18]	-	n log n	n log n	1	예	예	최악의 경우 O(n)의 데이터 이동을 수행한다. 이상적인 비교 정렬의 점근적 경계를 가지지만 이론적인 관심사일 뿐이다.

이론 컴퓨터 과학 분야에서는 특정 제약 조건을 가정하여 O(''n'' log ''n'')보다 더 나은 시간 복잡도를 가지는 다른 정렬 알고리즘들도 연구되었다.

'''토럽의 알고리즘''': 유한한 크기의 도메인에서 키를 정렬하는 무작위 알고리즘으로, O(''n'' log log ''n'') 시간과 O(''n'') 공간을 사용한다.^[19]
O(''n'' √(log log ''n''))의 예상 시간과 O(''n'') 공간을 사용하는 무작위 정수 정렬 알고리즘도 제안되었다.^[20]
위 알고리즘의 저자 중 한 명은 실수를 정렬하는 데 O(''n'' √log ''n'') 시간과 O(''n'') 공간을 사용하는 알고리즘을 발견했다고 주장했으며,^[21] 입력에 대한 추가 가정 없이 O(''n'' log ''n'' / √log log ''n'') 시간과 O(''n'') 공간을 달성하도록 수정될 수 있다고 주장한다.

5. 저명한 정렬 알고리즘

수많은 정렬 알고리즘이 존재하지만, 실제 구현에서는 몇몇 알고리즘이 주로 사용된다. 삽입 정렬은 작은 데이터 집합에 널리 사용되는 반면, 큰 데이터 집합에는 점근적으로 효율적인 정렬, 주로 힙 정렬, 합병 정렬 또는 퀵 정렬이 사용된다. 효율적인 구현은 일반적으로 하이브리드 알고리즘을 사용하여 전체 정렬에 점근적으로 효율적인 알고리즘과 재귀의 최하위 작은 목록에 삽입 정렬을 결합한다. 고도로 조정된 구현은 팀소트(Timsort) (병합 정렬, 삽입 정렬 및 추가 논리)와 같이 더 정교한 변형을 사용하며, 이는 안드로이드, 자바 및 파이썬에서 사용되고, 인트로소트(Introsort) (퀵 정렬 및 힙 정렬)는 일부 C++ sort 구현 및 .NET에서 (변형 형태로) 사용된다.

더 제한된 데이터, 예를 들어 고정된 간격의 숫자의 경우, 계수 정렬 또는 기수 정렬과 같은 분산 정렬이 널리 사용된다. 버블 정렬과 변형은 실제로는 거의 사용되지 않지만, 교육 및 이론적 논의에서 흔히 발견된다.

5. 1. 단순 정렬

가장 기본적인 정렬 방식으로는 삽입 정렬과 선택 정렬이 있다. 이 두 알고리즘은 구현이 비교적 간단하고 추가적인 메모리 사용량이 적은 제자리 정렬이라는 장점이 있어, 정렬할 데이터의 양이 적을 때는 효율적으로 사용될 수 있다. 특히 삽입 정렬은 이미 어느 정도 정렬된 데이터에 대해서는 매우 빠르게 동작하며, 선택 정렬은 데이터 이동(쓰기) 횟수를 최소화해야 하는 경우에 유용하다.

그러나 데이터의 양이 많아질수록 처리 시간이 급격하게 늘어나기 때문에(일반적으로 O(''n''²)의 시간 복잡도), 큰 규모의 데이터를 정렬하는 데는 적합하지 않다. 따라서 실제 환경에서는 퀵 정렬, 병합 정렬, 힙 정렬과 같은 더 복잡하지만 효율적인 알고리즘들이 주로 사용되며, 단순 정렬 알고리즘은 이들 효율적인 알고리즘 내부에서 작은 부분 문제를 해결하는 용도로 활용되기도 한다. 예를 들어, 하이브리드 알고리즘에서는 재귀적으로 문제를 분할하다가 데이터 크기가 일정 수준 이하로 작아지면 삽입 정렬을 사용하여 마무리하는 경우가 많다.

5. 1. 1. 삽입 정렬

삽입 정렬은 가장 단순한 정렬 알고리즘 중 하나로, 선택 정렬과 함께 낮은 부하로 인해 작은 데이터 집합이나 대부분의 요소가 이미 정렬된 리스트에 대해 효율적이다. 하지만 큰 데이터 집합에는 효율적이지 않다. 실제 환경에서는 비교 횟수가 적고 거의 정렬된 데이터에 대해 좋은 성능을 보이기 때문에, 일반적으로 선택 정렬보다 더 빠르고 선호되는 경향이 있다. 다만, 선택 정렬은 쓰기 횟수가 적으므로 쓰기 성능이 중요한 환경에서는 더 유용할 수 있다.

삽입 정렬은 제자리 정렬 알고리즘으로 분류되는데, 이는 정렬 과정에서 원본 데이터를 저장하는 공간 외에 추가로 필요한 저장 공간이 매우 적기 때문이다. 구체적으로, 원소를 옮겨 담을 임시 공간과 루프 제어 변수 정도의 공간만 추가로 사용한다.

알고리즘의 동작 방식은 리스트에서 아직 정렬되지 않은 요소를 하나씩 가져와 이미 정렬된 부분 리스트 내의 올바른 위치에 삽입하는 과정을 반복한다. 이는 마치 손에 든 카드를 정렬할 때 적절한 자리를 찾아 끼워 넣는 방식과 유사하다.^[54]^[22] 배열을 사용하여 구현할 경우, 정렬된 부분과 정렬되지 않은 부분이 같은 배열 공간을 공유할 수 있다. 그러나 특정 위치에 요소를 삽입하기 위해서는 그 뒤에 있는 모든 요소들을 한 칸씩 뒤로 이동시켜야 하므로, 이 이동 과정에서 비용이 많이 발생할 수 있다.

이러한 특징 때문에 삽입 정렬은 작은 데이터 집합을 정렬하는 데 널리 사용되며, 퀵 정렬이나 병합 정렬과 같은 더 복잡하고 효율적인 알고리즘의 일부로 사용되기도 한다. 예를 들어, 하이브리드 알고리즘에서는 전체적으로는 빠른 알고리즘을 사용하다가 데이터 크기가 일정 수준 이하로 작아지면 삽입 정렬로 전환하여 효율성을 높인다. 또한, 사람들이 종이나 책과 같은 물리적인 객체를 소량 정렬할 때 직관적으로 사용하는 방식이기도 하다.

삽입 정렬의 변형으로는 셸 정렬이 있으며, 이는 큰 리스트에서도 삽입 정렬보다 더 효율적으로 동작하도록 개선된 알고리즘이다.

5. 1. 2. 선택 정렬

''선택 정렬''은 제자리 정렬 비교 정렬 알고리즘의 하나이다. 빅 오 표기법으로 O(''n''²)의 시간 복잡도를 가지므로, 대규모 리스트에서는 비효율적이며, 일반적으로 유사한 삽입 정렬보다 성능이 떨어진다. 그러나 선택 정렬은 단순함으로 유명하며, 특정 상황에서는 더 복잡한 알고리즘보다 성능상의 이점을 갖는다.

이 알고리즘은 리스트에서 최소값을 찾아 첫 번째 위치의 값과 교환하고, 정렬되지 않은 나머지 리스트 부분에 대해 이 과정을 반복한다.^[23] 선택 정렬은 최대 ''n''번의 교환만 수행하므로, 데이터 교환(쓰기 연산) 비용이 많이 드는 상황에서 유용할 수 있다. 반면, 삽입 정렬은 비교 횟수가 적고 거의 정렬된 데이터에 대해 좋은 성능을 보이기 때문에 실제로는 선택 정렬보다 빠른 경우가 많다.

5. 2. 효율적인 정렬

실제로 널리 쓰이는 일반적인 정렬 알고리즘은 대부분 평균 시간 복잡도가 O(''n'' log ''n'')이며, 최악의 경우에도 비슷한 성능을 보이는 경우가 많다. 대표적으로 힙 정렬, 합병 정렬, 퀵 정렬이 여기에 속한다. 이 알고리즘들은 각기 장단점을 가지는데, 예를 들어 단순한 합병 정렬 구현은 O(''n'')의 추가 공간 복잡도를 필요로 하고, 단순한 퀵 정렬 구현은 최악의 경우 O(''n''²)의 시간 복잡도를 가질 수 있다. 이러한 단점은 더 복잡한 알고리즘 설계를 통해 해결하거나 개선할 수 있다.

실제 정렬 알고리즘을 구현할 때는 데이터의 크기나 특성에 따라 다른 전략을 사용한다. 데이터의 크기가 작을 때는 삽입 정렬처럼 구현이 간단하고 작은 데이터셋에서 효율적인 알고리즘이 주로 쓰인다. 반면, 데이터 크기가 클 때는 힙 정렬, 합병 정렬, 퀵 정렬과 같이 이론상 효율적인 O(''n'' log ''n'') 알고리즘들이 주로 사용된다.

많은 효율적인 구현은 하이브리드 방식을 채택한다. 이는 전체적으로는 대규모 데이터에 효율적인 알고리즘(예: 합병 정렬, 퀵 정렬)을 사용하되, 재귀적으로 작은 단위의 데이터를 처리할 때는 삽입 정렬로 전환하여 성능을 최적화하는 방식이다. 잘 최적화된 구현의 예로는 안드로이드, 자바, 파이썬 등에서 사용되는 팀소트(Timsort, 합병 정렬과 삽입 정렬 기반)나 일부 C++ 및 .NET 환경에서 사용되는 인트로소트(Introsort, 퀵 정렬과 힙 정렬 기반) 등이 있다.

데이터의 종류가 특정 범위의 숫자로 제한되는 등 특별한 경우에는 계수 정렬이나 기수 정렬과 같은 분산 정렬 알고리즘이 O(''n'' log ''n'') 알고리즘보다 더 효율적일 수 있어 널리 사용된다. 반면, 버블 정렬과 같은 일부 알고리즘은 실제 환경에서는 거의 사용되지 않지만, 알고리즘 교육이나 이론적인 논의에서는 자주 등장한다.

물리적인 물체(예: 서류, 책)를 정렬할 때 사람들은 직관적으로 작은 규모에서는 삽입 정렬과 유사한 방식을 사용하고, 큰 규모에서는 기준(예: 첫 글자)에 따라 그룹을 나누는 버킷 방식이나, 두 손을 활용하기 좋은 합병 정렬과 유사한 방식을 사용하기도 한다. 이는 컴퓨터 알고리즘의 효율성과는 다른 측면을 보여준다.

실제 데이터는 완전히 무작위적이지 않고 어느 정도 정렬되어 있거나 특정 패턴을 가지는 경우가 많다. 따라서 실용적인 정렬 알고리즘들은 이러한 실제 데이터의 특성을 고려하여 수정되기도 한다. 예를 들어, 이미 정렬된 데이터나 거의 정렬된 데이터에 대해 성능 저하가 발생하는 것을 방지하거나, 정렬 과정에서 원소들의 상대적인 순서가 유지되는 안정 정렬 속성을 만족시키기 위해 팀소트나 인트로소트와 같은 더 정교한 알고리즘이 개발되어 사용된다.

5. 2. 1. 합병 정렬

'''합병 정렬'''(Merge sort)은 이미 정렬된 목록들을 새로운 정렬된 목록으로 쉽게 합병할 수 있다는 점을 이용하는 정렬 알고리즘이다.^[24] 작동 방식은 먼저 모든 두 개의 요소(예: 1과 2, 그 다음 3과 4...)를 비교하고, 필요한 경우 순서를 바꾼다. 그런 다음, 이렇게 정렬된 길이 2의 목록들을 합병하여 길이 4의 정렬된 목록들을 만들고, 이 과정을 반복하여 최종적으로 두 개의 큰 목록을 하나의 정렬된 목록으로 합병한다.^[24]

합병 정렬은 최악의 경우에도 시간 복잡도가 O(''n'' log ''n'')이므로 매우 큰 목록을 정렬하는 데 효율적이다.^[24] 또한 데이터에 대한 임의 접근이 아닌 순차적 접근만 필요로 하므로 배열뿐만 아니라 목록에도 쉽게 적용할 수 있다는 장점이 있다. 그러나 추가적인 O(''n'')의 공간 복잡도를 가지며, 단순하게 구현할 경우 데이터 복사가 많이 발생할 수 있다는 단점이 있다. 합병 정렬은 대표적인 안정 정렬 알고리즘으로, 동일한 키 값을 가진 원소들의 상대적인 순서가 정렬 후에도 유지된다.

실용적인 일반 정렬 알고리즘들은 평균 시간 복잡도 O(''n'' log ''n'')의 알고리즘에 기반한 경우가 대부분이며, 힙 정렬, 합병 정렬, 퀵 정렬이 가장 흔하게 사용된다. 합병 정렬의 단순한 구현체는 O(''n'') 추가 공간을 사용하는 것이 특징이다. 이러한 알고리즘들은 실제 데이터를 다룰 때 효율성을 높이기 위해 수정되기도 한다. 예를 들어, 크기가 작은 데이터에 대해서는 삽입 정렬과 같은 다른 알고리즘으로 전환하는 하이브리드 알고리즘 방식이 사용된다.

합병 정렬은 온라인 알고리즘으로도 구현될 수 있다. 데이터가 순차적으로 들어올 때, 이미 정렬된 여러 개의 부분 리스트를 관리하다가 새 원소가 들어오면 적절한 리스트에 추가하고 필요에 따라 리스트들을 합병하는 방식으로 처리할 수 있다.

최근 합병 정렬은 실용적인 구현에서 인기가 높아졌는데, 대표적으로 팀소트(Timsort) 알고리즘에서 사용된다. 팀소트는 합병 정렬과 삽입 정렬 등을 결합한 정교한 알고리즘으로, 파이썬^[25]과 자바 (JDK 7^[26]부터)의 표준 정렬 방식으로 채택되었다. 합병 정렬 자체도 펄^[27]을 포함한 여러 프로그래밍 언어에서 표준 정렬 루틴으로 사용되었으며, 자바에서는 JDK 1.3^[28]부터 사용되어 왔다.

5. 2. 2. 힙 정렬

'''힙 정렬'''(Heapsort^eng)은 힙 자료 구조를 이용하여 가장 큰 (또는 가장 작은) 요소를 효율적으로 찾아내어 정렬하는 정렬 알고리즘이다. 이는 선택 정렬의 한 종류로 분류될 수 있다.

힙 정렬은 실용적으로 널리 사용되는 일반 정렬 알고리즘 중 하나로, 퀵 정렬, 합병 정렬과 함께 평균 시간 복잡도가 O(''n'' log ''n'')인 대표적인 알고리즘이다. 일반적으로 최악의 경우에도 O(''n'' log ''n'')의 시간 복잡도를 가진다.

큰 데이터 집합을 정렬할 때 점근적으로 효율적인 성능을 보여주기 때문에 많이 사용된다. 예를 들어, 인트로소트(Introsort)와 같은 하이브리드 알고리즘은 기본적으로 퀵 정렬을 사용하지만, 정렬 과정에서 성능 저하가 우려될 경우 힙 정렬로 전환하여 최악의 경우 시간 복잡도를 O(''n'' log ''n'')으로 보장한다.

다만, 사람이 물리적으로 객체를 정렬할 때는 직관적이지 않아 합병 정렬 등에 비해 사용하기 적합하지 않다는 특징이 있다.

5. 2. 3. 퀵 정렬

분할 정복 알고리즘의 하나로, 배열을 효과적으로 정렬하기 위해 '분할' 연산 방식을 사용한다. 이 과정에서 기준이 되는 특정 요소인 '피벗'을 선택한다.^[30]^[31] 배열 내에서 피벗보다 작은 모든 요소는 피벗의 앞으로, 피벗보다 큰 모든 요소는 피벗의 뒤로 옮겨진다. 이 분할 작업은 선형 시간 복잡도 내에서 효율적으로 이루어질 수 있으며, 추가적인 메모리 공간을 거의 사용하지 않는 제자리 정렬 방식으로 구현될 수 있다. 분할된 후에는 피벗을 기준으로 나뉜 두 개의 하위 배열(작은 요소들의 배열과 큰 요소들의 배열)에 대해 동일한 정렬 과정을 재귀적으로 반복한다.

퀵 정렬은 평균적으로 O(''n'' log ''n'')의 시간 복잡도를 가지며, 추가적인 부담(오버헤드)이 적어 널리 사용되는 정렬 알고리즘 중 하나이다. 제자리 정렬 방식으로 효율적인 구현이 가능하지만, 이 경우 일반적으로 불안정 정렬이 되며 구현이 다소 복잡할 수 있다. 그럼에도 불구하고 실제 환경에서는 가장 빠른 정렬 알고리즘 중 하나로 평가받는다. 퀵 정렬은 재귀 호출을 위한 스택 사용으로 인해 O(log ''n'')의 공간 복잡도를 가진다. 엄밀히 말해, 이 추가 공간 사용 때문에 정의상 제자리 정렬(O(1) 추가 공간)이 아닐 수 있지만, 필요한 추가 공간이 입력 크기 ''n''에 비해 상대적으로 매우 작기 때문에 실용적인 관점에서는 흔히 제자리 정렬로 간주된다. 이러한 평균적인 빠른 성능과 상대적으로 적은 추가 공간 사용 덕분에 많은 표준 프로그래밍 라이브러리에 포함되어 있다.

퀵 정렬의 주요 단점은 최악의 경우 O(''n''²)의 시간 복잡도를 가질 수 있다는 점이다. 이러한 최악의 상황은 드물게 발생하지만, 단순한 구현 방식(예: 배열의 첫 번째나 마지막 요소를 피벗으로 선택)에서는 이미 정렬된 데이터와 같이 특정 형태의 입력에 대해 발생하기 쉽다. 따라서 퀵 정렬의 성능은 좋은 피벗을 어떻게 선택하는지에 크게 좌우된다. 만약 피벗을 지속적으로 잘못 선택하면 성능은 O(''n''²)로 현저히 저하될 수 있지만, 좋은 피벗을 선택하면 점근적으로 최적인 O(''n'' log ''n'') 성능을 기대할 수 있다. 예를 들어, 매 단계에서 배열의 중앙값을 피벗으로 선택하면 O(''n'' log ''n'') 성능이 보장된다. 그러나 정렬되지 않은 목록에서 중앙값을 찾는 것(중앙값의 중앙값 선택 알고리즘 등) 자체가 O(''n'') 연산을 필요로 하므로, 이는 정렬 과정에 상당한 추가 비용을 발생시킨다. 실제 구현에서는 임의의 요소를 피벗으로 선택하는 방식이 주로 사용되며, 이는 거의 확실하게 O(''n'' log ''n'') 성능을 보장한다.

최악의 경우에도 O(''n'' log ''n'') 성능을 보장해야 하는 상황에서는 몇 가지 개선 방법이 사용된다. Musser가 제안한 아이디어 중 하나는 재귀 호출의 최대 깊이를 제한하는 것이다.^[32] 재귀 깊이가 특정 한계(예: 1 + 2 * floor(log₂(''n'')), 이는 무작위 배열에서 예상되는 평균 최대 재귀 깊이의 약 두 배)를 초과하면, 힙 정렬과 같이 최악의 경우에도 O(''n'' log ''n'') 성능이 보장되는 다른 알고리즘으로 전환하여 정렬을 계속한다. 이러한 방식을 사용하는 대표적인 하이브리드 알고리즘으로 인트로소트(Introsort)가 있다.

5. 2. 4. 셸 소트

셸 정렬(Shellsort)은 요소들을 여러 번의 교환 위치로 이동시킨다는 점에서 버블 정렬(bubble sort)과 다르다.

'''셸 정렬'''(Shellsort)은 1959년 도널드 셸(Donald Shell)이 발명한 정렬 알고리즘이다.^[33] 이 알고리즘은 삽입 정렬을 개선한 것으로, 정렬되지 않은 요소들을 한 번에 여러 위치씩 이동시키는 방식을 사용한다.

셸 정렬의 기본 아이디어는 삽입 정렬이 O(''kn'') 시간에 수행된다는 점에 착안한 것이다. 여기서 ''k''는 위치가 잘못된 두 요소 간의 최대 거리를 의미한다. 삽입 정렬은 일반적으로 O(''n''²)의 시간 복잡도를 가지지만, 대부분 정렬된 상태에서 몇 개의 요소만 제자리에 있지 않은 경우에는 더 빠르게 작동한다. 셸 정렬은 이러한 삽입 정렬의 특징을 활용하여, 처음에는 멀리 떨어진 요소들을 먼저 정렬하고 점차 그 간격을 줄여나가면서 최종적으로는 훨씬 빠르게 정렬을 완료한다. 예를 들어, 데이터를 2차원 배열처럼 간주하고 각 열에 대해 삽입 정렬을 수행하는 방식으로 구현할 수 있다.

셸 정렬의 최악 시간 복잡도는 아직 미해결 문제로 남아 있으며, 어떤 간격(gap) 시퀀스를 사용하느냐에 따라 달라진다. 알려진 복잡도는 O(''n''²)부터 O(''n''^4/3), Θ(''n'' log² ''n'')까지 다양하다.

셸 정렬은 제자리 정렬 알고리즘이며, 비교적 적은 양의 코드로 구현할 수 있고 호출 스택을 사용하지 않는다는 장점이 있다. 이러한 특징 때문에 메모리가 제한적인 임베디드 시스템이나 운영 체제 커널 등에서 유용하게 사용될 수 있다.

5. 3. 거품 정렬 및 변종

버블 정렬과 빗 정렬, 칵테일 정렬과 같은 변형은 단순하지만 매우 비효율적인 정렬 알고리즘이다. 분석이 용이하기 때문에 입문서에서 자주 볼 수 있지만, 실제로는 거의 사용되지 않는다.

5. 3. 1. 버블 정렬

버블 정렬의 예시. 목록을 반복하며 인접한 항목의 순서가 맞지 않으면 교환한다.

버블 정렬(Bubble sort)은 빗 정렬, 칵테일 정렬과 같은 변형들과 함께 단순하지만 매우 비효율적인 정렬 알고리즘으로 알려져 있다. 알고리즘의 작동 원리는 데이터 집합의 처음부터 시작하여 인접한 두 요소를 비교하고, 만약 첫 번째 요소가 두 번째 요소보다 크면 두 요소의 위치를 교환하는 방식이다. 이 비교와 교환 과정을 데이터 집합의 끝까지 진행하며, 한 번의 전체 순회가 끝난 후 다시 처음부터 이 과정을 반복한다. 더 이상 교환이 발생하지 않을 때까지, 즉 모든 요소가 정렬될 때까지 이 과정을 계속한다.^[34]

이 알고리즘의 평균 시간 복잡도와 최악의 경우 시간 복잡도는 모두 O(''n''²)이다. 이는 데이터의 양(''n'')이 증가함에 따라 필요한 연산 횟수가 제곱으로 늘어난다는 의미로, 크거나 정렬되지 않은 데이터 집합을 다룰 때는 성능이 매우 낮아져 거의 사용되지 않는다.

하지만 버블 정렬은 알고리즘 자체가 매우 간단하여 이해하고 구현하기 쉽다는 장점이 있다. 따라서 정렬해야 할 데이터의 수가 아주 적을 때는 비효율성이 크게 문제되지 않아 사용될 수 있다. 또한, 데이터가 이미 거의 정렬되어 있는 상태, 즉 대부분의 요소가 제자리에 있고 일부 요소만 약간의 위치 이동이 필요한 경우에는 비교적 효율적으로 작동할 수 있다. 예를 들어, 리스트 내의 모든 요소가 최대 한 칸만 제자리에서 벗어나 있는 경우, 버블 정렬은 첫 번째 순회(pass)에서 대부분의 교환을 완료하고, 두 번째 순회에서 정렬이 완료되었음을 확인하게 된다. 이런 특별한 경우 버블 정렬은 약 2''n'' 정도의 시간 복잡도를 가질 수 있다.^[35] 분석의 용이성 때문에 입문 교육 과정이나 이론 설명에서는 자주 등장하지만, 실제 프로그래밍 환경에서는 거의 쓰이지 않는다.

5. 3. 2. 빗질 정렬

''빗질 정렬''은 버블 정렬을 기반으로 하는 비교적 간단한 정렬 알고리즘으로, 원래 1980년 Włodzimierz Dobosiewicz에 의해 설계되었다.^[36] 이후 Stephen Lacey와 Richard Box가 1991년 4월에 발행된 ''바이트'' 매거진 기사를 통해 재발견하고 널리 알렸다.

빗질 정렬의 기본 아이디어는 버블 정렬에서 정렬 속도를 크게 떨어뜨리는 요인인 ''거북이'', 즉 리스트 끝부분 근처에 있는 작은 값들을 효과적으로 제거하는 것이다. (리스트 앞부분의 큰 값인 ''토끼''는 버블 정렬에서 큰 문제가 되지 않는다.) 이를 위해 처음에는 배열 내에서 서로 특정 거리만큼 떨어져 있는 요소들을 비교하고 교환한다. 이후 비교하는 요소들 사이의 거리를 점차 줄여나가, 마지막에는 인접한 요소만을 비교하고 교환하는 일반적인 버블 정렬처럼 작동하게 된다.

이러한 방식은 셸 정렬이 삽입 정렬을 일반화하여 서로 특정 거리만큼 떨어진 요소들을 교환하는 것과 유사하게, 빗질 정렬은 버블 정렬에 같은 아이디어를 적용한 것으로 볼 수 있다.

5. 4. 분산 정렬

''분산 정렬''은 데이터를 입력에서 여러 개의 중간 구조로 분배한 다음, 이를 수집하여 출력에 배치하는 모든 정렬 알고리즘을 지칭한다. 예를 들어, 버킷 정렬과 플래시 정렬 모두 분산 기반 정렬 알고리즘이다. 분산 정렬 알고리즘은 단일 프로세서에서 사용할 수도 있고, 개별 하위 집합을 서로 다른 프로세서에서 별도로 정렬한 다음 결합하는 분산 알고리즘일 수도 있다. 이를 통해 단일 컴퓨터의 메모리에 맞지 않는 대량의 데이터를 정렬하는 외부 정렬에도 활용될 수 있다.

5. 4. 1. 계수 정렬

계수 정렬은 각 입력값이 특정 가능한 값들의 집합 ''S'' 안에 속한다는 것을 미리 알고 있을 때 적용할 수 있는 정렬 알고리즘이다. 예를 들어, 정렬하려는 숫자들의 범위가 0부터 100 사이라는 것을 안다면 계수 정렬을 사용할 수 있다.

이 알고리즘의 시간 복잡도는 O(|''S''| + ''n'')이며, 필요한 추가 메모리는 O(|''S''|)이다. 여기서 ''n''은 정렬할 항목의 개수이고, |''S''|는 가능한 값의 종류(범위)의 크기를 의미한다.

계수 정렬의 작동 방식은 다음과 같다.

1. 먼저, 가능한 값의 범위 크기(|''S''|)만큼의 크기를 가지는 정수 배열(계수 배열)을 만든다. 이 배열의 각 칸은 특정 값이 입력 데이터에 몇 번 나타나는지를 세는 데 사용된다. 예를 들어, ''i''번째 칸은 값 ''i''가 몇 번 나왔는지를 저장한다.

2. 입력 데이터를 하나씩 읽으면서, 해당 값에 해당하는 계수 배열의 칸의 숫자를 1씩 증가시킨다. 모든 입력 데이터를 처리하면, 계수 배열에는 각 값이 몇 번씩 등장했는지 기록된다.

3. 마지막으로, 계수 배열을 처음부터 순서대로 확인하면서, 각 칸에 기록된 횟수만큼 해당 값을 출력 배열에 채워 넣으면 정렬된 결과를 얻을 수 있다.

계수 정렬은 가능한 값의 범위 ''S''가 너무 크지 않다면 매우 빠른 성능을 보인다. 특히 입력 데이터의 개수 ''n''이 증가할수록 효율성이 좋다. 하지만 값의 범위 |''S''|가 매우 크다면, 계수 배열을 만드는 데 많은 메모리가 필요하게 되어 비효율적일 수 있다. 이런 이유로 항상 사용될 수 있는 알고리즘은 아니다.

또한, 계수 정렬은 안정 정렬이 되도록 구현할 수 있다. 안정 정렬은 같은 값을 가지는 원소들의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식을 말한다.

5. 4. 2. 버킷 정렬

분산 정렬의 한 종류로, 배열을 유한한 개수의 '버킷'(bucket, 양동이)으로 나누어 정렬하는 분할 정복 방식의 정렬 알고리즘이다. 먼저 입력 데이터를 여러 버킷에 분배하고, 각 버킷에 속한 데이터들을 개별적으로 정렬한다. 이때 각 버킷의 정렬은 다른 정렬 알고리즘을 사용하거나, 버킷 정렬 자체를 재귀적으로 적용하여 수행할 수 있다. 모든 버킷의 정렬이 완료되면, 버킷 순서대로 데이터를 이어 붙여 전체 데이터의 정렬을 완성한다.

버킷 정렬은 입력 데이터가 모든 버킷에 걸쳐 균등하게 분포될 때 가장 좋은 성능을 보인다. 데이터가 특정 버킷에 몰려 있다면 효율성이 떨어질 수 있다.

5. 4. 3. 기수 정렬

''기수 정렬''은 개별 자릿수를 기준으로 숫자를 정렬하는 정렬 알고리즘이다. 각각 ''k''개의 자릿수를 가진 ''n''개의 숫자를 정렬하는 데 걸리는 시간 복잡도는 O(''n'' · ''k'')이다. 기수 정렬은 숫자의 자릿수를 최하위 자릿수(LSD)부터 처리하거나 최상위 자릿수(MSD)부터 처리할 수 있다.

LSD 방식은 안정 정렬을 사용하여 같은 값의 상대적 순서를 유지하면서, 최하위 자릿수부터 정렬하기 시작한다. 이후 다음 자릿수를 기준으로 정렬하는 과정을 최상위 자릿수까지 반복하여 전체 목록을 정렬한다. LSD 기수 정렬은 반드시 안정 정렬을 사용해야 하지만, MSD 기수 정렬은 안정성이 요구되지 않는다면 그럴 필요가 없다. 제자리 MSD 기수 정렬은 안정적이지 않다.

계수 정렬 알고리즘이 기수 정렬의 각 자릿수 정렬 단계에서 흔히 사용된다. 작은 크기의 그룹(버킷)에 삽입 정렬을 적용하는 것과 같은 하이브리드 알고리즘 방식을 사용하면 기수 정렬의 성능을 크게 향상시킬 수 있다.

참조

_[1] 웹사이트 Meet the 'Refrigerator Ladies' Who Programmed the ENIAC http://mentalfloss.c[...] 2016-06-16
_[2] 뉴스 Frances E. Holberton, 84, Early Computer Programmer https://www.nytimes.[...] NYTimes 2014-12-16
_[3] 간행물 Electronic Data Sorting Stanford University
_[4] 서적 Introduction To Algorithms https://books.google[...] The MIT Press
_[5] 학술지 Fast Stable Merging and Sorting in Constant Extra Space 1992-12
_[6] 학술회 An {{math|O(n log n)}} sorting network
_[7] 웹사이트 Sortierverfahren http://dbs.uni-leipz[...] 2022-03-01
_[8] 학술회 Ratio Based Stable In-Place Merging
_[9] 서적 Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 https://books.google[...] Pearson Education 2012-11-27
_[10] 학술지 Implementing Quicksort programs
_[11] 웹사이트 SELECTION SORT (Java, C++) – Algorithms and Data Structures http://www.algolist.[...] 2018-04-14
_[12] 서적 Introduction To Algorithms https://books.google[...] The MIT Press
_[13] 학술지 The Fastest Sorting Algorithm? http://www.drdobbs.c[...] 2015-11-23
_[14] 서적 Introduction to Algorithms
_[15] 서적 Algorithm Design: Foundations, Analysis, and Internet Examples John Wiley & Sons
_[16] 논문 Is this the simplest (and most surprising) sorting algorithm ever? 2021-10-03
_[17] 서적 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 http://www.hermann-g[...] Springer-Verlag 2007
_[18] 학술지 Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves 2007-06
_[19] 학술지 Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations 2002-02
_[20] 학술회 Integer sorting in O(n√(log log n)) expected time and linear space
_[21] 학술지 Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space https://doi.org/10.1[...] 2020-04-01
_[22] 서적 Algorithms & Data Structures Prentice-Hall
_[23] 서적
_[24] 서적
_[25] 웹사이트 Tim Peters's original description of timsort http://svn.python.or[...] 2018-04-14
_[26] 웹사이트 OpenJDK's TimSort.java http://cr.openjdk.ja[...] 2018-04-14
_[27] 웹사이트 sort – perldoc.perl.org http://perldoc.perl.[...] 2018-04-14
_[28] 웹사이트 Merge sort in Java 1.3 http://java.sun.com/[...]
_[29] 서적
_[30] 서적
_[31] 서적 Introduction to Algorithms The MIT Press
_[32] 학술지 Introspective Sorting and Selection Algorithms
_[33] 학술지 A High-Speed Sorting Procedure http://penguin.ewu.e[...] 2020-03-23
_[34] 서적
_[35] 웹사이트 kernel/groups.c https://github.com/t[...] 2012-05-05
_[36] 논문 Analyzing variants of Shellsort 2001-09-15
_[37] 웹사이트 Exchange Sort Algorithm https://www.codingun[...] 2021-07-10
_[38] 웹사이트 Exchange Sort https://mathbits.com[...] 2021-07-10
_[39] 웹사이트 tag sort Definition from PC Magazine Encyclopedia https://www.pcmag.co[...] 2018-04-14
_[40] 서적 The Art of Computer Programming Addison-Wesley
_[41] 서적 Fundamentals of Data Structures H. Freeman & Co.
_[42] 웹사이트 ソート https://kotobank.jp/[...] コトバンク 2020-06-01
_[43] 문서 Bubble Sort: An Archaeological Algorithmic Analysis http://www.cs.duke.e[...]
_[44] 문서 tag sort Definition http://www.pcmag.com[...] PCMAG.COM
_[45] URL http://www.cs.duke.e[...]
_[46] 웹인용 Meet the 'Refrigerator Ladies' Who Programmed the ENIAC http://mentalfloss.c[...] 2013-10-13
_[47] 뉴스 Frances E. Holberton, 84, Early Computer Programmer https://www.nytimes.[...] NYTimes 2001-12-17
_[48] 논문 Electronic Data Sorting Stanford University
_[49] 서적 Introduction To Algorithms https://books.google[...] The MIT Press
_[50] 웹인용 보관된 사본 http://dbs.uni-leipz[...] 2019-11-19
_[51] 간행물 Unshuffle, Not Quite a Sort 1985-11
_[52] 간행물 Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves 2007-06
_[53] 간행물 The Fastest Sorting Algorithm? http://www.drdobbs.c[...]
_[54] 서적 Algorithms & Data Structures Prentice-Hall
_[55] harvnb

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com