Sorting Algorithm

OpenCSTL은 컨테이너 원소의 타입·규모·안정성 요구에 맞춰 선택할 수 있도록 6가지 정렬 알고리즘을 제공합니다. 모든 저수준 정렬 함수는 qsort와 동일한 (void* base, size_t nmemb, size_t size, int (*cmp)(const void*, const void*)) 시그니처를 따르므로 libc qsort와 상호 치환이 가능합니다(단, rsort는 예외).

qsort: Default qsort (stdlib.h)
msort: Merge sort
tsort: Tim sort
pdqsort: Pattern-defeating Quicksort
rsort: LSD Radix sort
pmsort: Parallel Merge sort (pthread 사용)

output.mp4

Algorithms

1.1 😭 `qsort` — Default qsort

stdlib.h에서 제공하는 표준 qsort를 그대로 사용합니다. 별도 구현 없이 <stdlib.h>의 구현에 의존하므로 플랫폼과 컴파일러(특히 MSVC와 GCC)에 따라 성능 편차가 큽니다. 비교 기반, 불안정 정렬이며, 일반적으로 introsort/quicksort로 구현되어 있습니다.

안전성: Unstable
시간복잡도: O(N log N) 평균, O(N²) 최악(구현에 따라 다름)
공간복잡도: O(log N)
사용처: 외부 의존성 없는 폴백(fallback). bestsort.h에서 TCC + macOS/Linux 조합의 unstable_sort 기본값으로 쓰입니다.

1.2 🔥 `msort` — Merge sort

bottom-up iterative merge sort입니다. 내부적으로 MSORT_ISORT_THRESH = 32 블록 단위로 먼저 binary insertion sort([isort](https://github.com/springkim/OpenCSTL/blob/master/opencstl/isort.h))로 정렬한 뒤 병합을 수행합니다. 병합 단계에서는 이미 정렬된 경계(a[len1-1] <= a[len1])를 감지해 병합을 건너뛰며, len1 <= len2에 따라 좌측/우측 중 작은 쪽만 보조 버퍼로 복사하는 "smaller half buffering" 최적화를 사용합니다.

void msort(void *base, size_t number, size_t width, CSTL_COMPARE compare);

안전성: Stable
시간복잡도: O(N log N) (최선·평균·최악 모두)
공간복잡도: O(N/2) (보조 버퍼 calloc((nmemb+1)/2, size))
특징: 캐시 지역성이 준수하고, 이미 정렬된 구간에서 병합을 건너뛰어 부분 정렬 입력에 강합니다. Clang/Linux 환경에서 가장 빠른 안정 정렬이어서 해당 조합의 stable_sort로 선택됩니다.

1.3 🎉 `tsort` — Tim sort

Python,Java의 Timsort를 C로 최적화 한 구현입니다. 입력을 Natural run으로 분할하고, 각 런이 minrun(32~64) 미만이면 binary insertion sort로 확장합니다. 분할된 런은 스택에 쌓고 merge_collapse 불변식을 유지하며 병합합니다. Galloping mode를 지원해 한쪽 시퀀스에서 연속된 원소가 반대쪽을 크게 앞지를 때 이진 탐색 기반 점프 병합으로 전환합니다.

void tsort(void *base, const size_t number, const size_t width, CSTL_COMPARE cmp);

안전성: Stable
시간복잡도: O(N) 최선(이미 정렬된 경우), O(N log N) 평균·최악
공간복잡도: O(N) (보조 버퍼 malloc(len * sz))
특징: 실세계의 부분 정렬 입력에 대해 거의 선형 시간에 가까운 성능을 보입니다. 대부분의 OS/컴파일러 조합에서 stable_sort의 기본값입니다.

1.4 🙏 `pdqsort` — Pattern-defeating Quicksort

Orson Peters의 pdqsort를 C로 포팅한 구현입니다. 핵심 아이디어 세 가지를 결합합니다.

Bad partition 카운팅: 분할이 N/8보다 불균형하면 bad 카운터를 감소시키고, 0이 되면 힙 정렬로 폴백(introsort 동작). 임계값 PDQ_ISORT_THRESH = 24.
Pattern breaking: 불균형이 감지되면 피벗 주변 원소들을 셔플하여 적대적 입력(adversarial input)을 무력화합니다.
Partial insertion sort: 분할 후 8회 미만의 이동으로 완료되면 즉시 종료합니다.

pdqsort(void *base, size_t number, size_t width, CSTL_COMPARE cmp);

안전성: Unstable
시간복잡도: O(N log N) 최악(힙 폴백으로 보장), 부분 정렬 입력에서 O(N)에 근접
공간복잡도: O(log N) (명시적 재귀 스택 PDQ_MAX_STACK)
특징: 불안정 정렬 중 평균 성능이 가장 우수합니다. 대부분의 플랫폼에서 sort의 기본값입니다.

불안정 정렬이 더 빠른것은 아닙니다. 컴파일러/OS에 따라 msort, tsort가 더 빠를 수 있습니다.

1.5 👀 `rsort` — LSD Radix sort

32비트·64비트 정수 전용 Least Significant Digit 기수 정렬입니다. 1바이트(256 버킷) 단위로 4회(32비트) 또는 8회(64비트) 패스를 수행하며, 부호 비트를 XOR 마스킹(key ^ sign_mask)해 부호 있는 정수를 올바른 순서로 정렬합니다.

#define rsort(base, n) // type-checked macro
// 내부 구현
static void rsort32(int32_t *__base, size_t n);
static void rsort64(int64_t *__base, size_t n);

타입 검증은 sizeof(*base) == 4 || sizeof(*base) == 8 정적 assertion으로 수행되며, 비교 함수(cmp)가 필요 없습니다.

안정성: Stable
시간잡도: O(N · k) (k는 바이트 수: 4 또는 8)
공간복잡도: O(N) (보조 버퍼)
제약: int32_t/int64_t(또는 동일 크기의 정수형)에만 사용 가능. 실수·문자열·구조체에는 사용할 수 없습니다.
특징: 비교 기반이 아니므로 N log N 하한을 돌파합니다. 벤치마크상 정수 정렬에서 압도적으로 빠릅니다.

1.6 `pmsort` — Parallel Merge sort

pthreads 기반 병렬 머지 소트입니다. PS_SEQ_CUTOFF 이하의 구간은 msort로 순차 처리하고, 그 이상에서는 좌/우 부분을 별도 스레드로 분기합니다. 재귀 깊이가 PS_MAX_DEPTH에 도달하면 추가 분기를 멈추고 순차 실행합니다.

void pmsort(void *base, const size_t number, const size_t width, CSTL_COMPARE cmp);

안정성: Stable (msort를 베이스로 함)
시간복잡도: O(N log N / P + N) (P는 가용 코어 수)
공간복잡도: O(N) (전체 범위 보조 버퍼 malloc(len * size_elem))
특징: 대규모 입력(벤치마크 기준 수천 ms 단위)에서만 이득이 있으며, 작은 입력에서는 msort로 자동 폴백됩니다. TCC 환경에서는 pthreads 스핀업 비용 대비 이득이 커 가장 큰 가속을 보입니다.

2. Feature comparison

Algorithm	Stable	Best	Average	Worst	Extra Space	Comparator	Notes
`qsort`	❌	`O(N log N)`	`O(N log N)`	`O(N²)`*	`O(log N)`	✅	libc 의존
`msort`	✅	`O(N log N)`	`O(N log N)`	`O(N log N)`	`O(N/2)`	✅	부분 정렬에 강함
`tsort`	✅	`O(N)`	`O(N log N)`	`O(N log N)`	`O(N)`	✅	자연 런 + 갤러핑
`pdqsort`	❌	`O(N log N)`	`O(N log N)`	`O(N log N)`	`O(log N)`	✅	힙 폴백 보장
`rsort`	✅	`O(N · k)`	`O(N · k)`	`O(N · k)`	`O(N)`	❌	int32/int64 전용
`pmsort`	✅	`O(N log N / P)`	`O(N log N / P)`	`O(N log N)`	`O(N)`	✅	pthreads 필요

* qsort의 최악 시간복잡도는 libc 구현에 따라 다릅니다(대부분의 최신 libc는 introsort로 O(N log N) 보장).

3. Selection guide

어떤 정렬을 선택할지 애매할 때는 다음 순서로 결정하세요.

원소가 int32_t/int64_t이고 비교 기준이 자연 순서인가? → rsort
안정 정렬이 필요한가? (동일 키 원소의 상대 순서 보존)
- 대규모(수백만 개 이상) + 멀티코어 가용 → pmsort
- 일반적인 경우 → tsort (부분 정렬 입력) / msort (랜덤 입력)
안정성이 불필요한가? → pdqsort
라이브러리 의존성을 최소화하고 싶은가? → qsort 직접 고르기 어렵다면 bestsort.h가 정의하는 cstl_best_stable_sort / cstl_unstable_sort를 사용하세요. 이는 현재 OS·컴파일러에서 경험적으로 가장 빠른 구현을 자동 선택합니다.

4. `bestsort.h` — Platform-aware auto selection

bestsort.h는 컴파일 타임에 OCSTL_OS_*와 OCSTL_CC_* 매크로를 조합해 아래 표처럼 기본 정렬을 선택합니다.

OS	Compiler	`cstl_best_stable_sort`	`cstl_unstable_sort`
macOS	Clang	`msort`	`pdqsort`
macOS	GCC	`tsort`	`pdqsort`
macOS	TCC	`tsort`	`qsort`
Linux	Clang	`msort`	`pdqsort`
Linux	GCC	`tsort`	`pdqsort`
Linux	TCC	`tsort`	`qsort`
Windows	Clang	`tsort`	`pdqsort`
Windows	GCC	`tsort`	`pdqsort`
Windows	MSVC	`tsort`	`pdqsort`
Windows	TCC	`tsort`	`pdqsort`
(any)	NVCC	`tsort`	`pdqsort`

이 매핑은 아래의 벤치마크 결과를 근거로 정해졌습니다.

5. Benchmark

단위는 ms(낮을수록 빠름). 동일 입력에 대한 벽시계 시간입니다. 굵게 표시한 값은 해당 환경의 최우수 결과입니다.

5.1 AMD Ryzen AI 9 HX 370

ENV/SORTING	qsort	msort	tsort	pdqsort	rsort	pmsort
Windows/GCC	3632.33	1985.04	1897.76	1731.67	834.42	904.90
Windows/Clang	3579.19	1507.26	1864.56	1667.96	832.88	929.84
Windows/MSVC	3735.54	2239.40	2031.28	2840.16	900.42	934.35
Windows/TCC	5906.01	5467.04	5234.41	6196.76	2639.43	1374.25
Windows/NVCC	3552.48	3341.63	3122.72	3041.80	845.77	818.91

5.2 Intel(R) Core(TM) Ultra 9 288V

ENV/SORTING	qsort	msort	tsort	pdqsort	rsort	pmsort
Linux/GCC	3062.21	1910.44	1880.95	1718.06	1144.05	928.33
Linux/Clang	2957.69	1500.27	1706.21	1637.62	1197.66	977.43
Linux/TCC	3375.22	3752.22	3594.69	4418.40	1681.73	1049.11

5.3 Apple M4(10 Cores)

ENV/SORTING	qsort	msort	tsort	pdqsort	rsort	pmsort
MacOS/GCC	2225.84	1533.00	1465.56	1375.61	937.60	660.07
MacOS/Clang	2221.72	1514.17	2577.13	1342.28	928.88	671.22
MacOS/TCC	3256.99	4780.36	4292.07	5024.01	2516.91	1042.61

5.4 관찰 포인트

정수형 데이터라면 rsort가 거의 대부분 이긴다. 데스크톱 x86에서 비교 기반 정렬은 구조적으로 기수 정렬을 넘기 어렵습니다.
TCC 환경은 비교 함수 호출 오버헤드가 크기 때문에 비교 기반 알고리즘이 전반적으로 느리며, 대신 pmsort의 병렬화 이득이 극단적으로 큽니다(Windows/TCC에서 4배 이상 가속).
MSVC의 pdqsort는 GCC/Clang보다 느린데, 인라인·branch prediction 힌트 처리가 약해 나타나는 현상입니다. MSVC에서는 tsort를 고르는 편이 안전합니다.
Apple Silicon 및 Linux의 Clang에서는 msort가 tsort를 앞섭니다. 해당 조합에서 cstl_best_stable_sort가 msort로 정의된 이유입니다.

6. High-level API

컨테이너 기반의 고수준 래퍼가 두 가지 제공됩니다.

6.1 `cstl_sort` / `cstl_stable_sort`

컨테이너(vector, list, deque)를 감지해 적절한 정렬 함수를 자동으로 디스패치합니다.

#include "opencstl.h"
 
int cmp_int(const void *a, const void *b) {
    int x = *(const int *) a, y = *(const int *) b;
    return (x > y) - (x < y);
}
 
int main(void) {
    VECTOR(int) v = new_vector(int);

    for (int i = 10; i >= 1; --i) {
        push_back(v, i);
    }
 
    // 불안정 정렬: vector/deque → cstl_unstable_sort,     list → qsort 기반
    sort(v, cmp_int);
 
    // 안정 정렬: vector/deque → cstl_best_stable_sort,    list → msort 기반
    stable_sort(v, cmp_int);
 
    destroy(v);
    return 0;
}

비교 함수를 생략하면 타입 이름 기반 기본 비교자(LESS(type_name))가 선택되고, 그마저 없으면 memcmp가 폴백으로 사용됩니다.

매크로	디스패치 대상
`sort` (vector/deque)	`unstable_sort` (= 플랫폼별 기본 불안정 정렬)
`sort` (list)	리스트 전용 quicksort(`__cstl_list_qsort`)
`stable_sort` (vector/deque)	`stable_sort` (= 플랫폼별 기본 안정 정렬)
`stable_sort` (list)	리스트 전용 merge sort(`__cstl_list_msort`)

6.2 `C++ 컴파일러`

C++ 컴파일러에서는 sort 대신 csort가 정의되고, stable_sort 대신 cstable_sort를 사용해야 합니다.

6.3 저수준 직접 호출

배열에 대해 특정 알고리즘을 명시적으로 쓰고 싶을 때는 함수를 직접 호출합니다.

#include "opencstl.h"
 
int main(void) {
    int arr[] = {5, 2, 8, 1, 9, 3};
    size_t n = sizeof(arr) / sizeof(arr[0]);
 
    // 안정 정렬
    tsort(arr, n, sizeof(int), cmp_int);
    msort(arr, n, sizeof(int), cmp_int);
    pmsort(arr, n, sizeof(int), cmp_int);
 
    // 불안정 정렬
    pdqsort(arr, n, sizeof(int), cmp_int);
    qsort(arr, n, sizeof(int), cmp_int);
 
    // 정수 전용 기수 정렬 (cmp 불필요)
    rsort(arr, n);
 
    return 0;
}

7. See also

OpenCSTL Wiki

Home
- Container library
  - Sequential Containers
    - VECTOR
    - DEQUE
    - LIST
  - Associative Containers
    - SET
    - MAP
  - Unordered Containers
    - UNORDERED_SET
    - UNORDERED_MAP
- Sorting Algorithm
- Logging library

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Sorting Algorithm

Algorithms

1.1 😭 `qsort` — Default qsort

1.2 🔥 `msort` — Merge sort

1.3 🎉 `tsort` — Tim sort

1.4 🙏 `pdqsort` — Pattern-defeating Quicksort

1.5 👀 `rsort` — LSD Radix sort

1.6 `pmsort` — Parallel Merge sort

2. Feature comparison

3. Selection guide

4. `bestsort.h` — Platform-aware auto selection

5. Benchmark

5.1 AMD Ryzen AI 9 HX 370

5.2 Intel(R) Core(TM) Ultra 9 288V

5.3 Apple M4(10 Cores)

5.4 관찰 포인트

6. High-level API

6.1 `cstl_sort` / `cstl_stable_sort`

6.2 `C++ 컴파일러`

6.3 저수준 직접 호출

7. See also

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

OpenCSTL Wiki

Clone this wiki locally

Sorting Algorithm

Algorithms

1.1 😭 qsort — Default qsort

1.2 🔥 msort — Merge sort

1.3 🎉 tsort — Tim sort

1.4 🙏 pdqsort — Pattern-defeating Quicksort

1.5 👀 rsort — LSD Radix sort

1.6 pmsort — Parallel Merge sort

2. Feature comparison

3. Selection guide

4. bestsort.h — Platform-aware auto selection

5. Benchmark

5.1 AMD Ryzen AI 9 HX 370

5.2 Intel(R) Core(TM) Ultra 9 288V

5.3 Apple M4(10 Cores)

5.4 관찰 포인트

6. High-level API

6.1 cstl_sort / cstl_stable_sort

6.2 C++ 컴파일러

6.3 저수준 직접 호출

7. See also

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

OpenCSTL Wiki

Clone this wiki locally

1.1 😭 `qsort` — Default qsort

1.2 🔥 `msort` — Merge sort

1.3 🎉 `tsort` — Tim sort

1.4 🙏 `pdqsort` — Pattern-defeating Quicksort

1.5 👀 `rsort` — LSD Radix sort

1.6 `pmsort` — Parallel Merge sort

4. `bestsort.h` — Platform-aware auto selection

6.1 `cstl_sort` / `cstl_stable_sort`

6.2 `C++ 컴파일러`