---
id: "imported/ps/algorithm/sort/radix"
title: "Radix Sort"
description: "Radix Sort 관련 기록."
kind: "record"
published: "2023-08-08T00:00:00.000Z"
tags: []
url: "https://www.readiz.com/notes/algorithm/sort/radix/"
markdownUrl: "https://www.readiz.com/notes/algorithm/sort/radix/index.md"
---

# Radix Sort

## Radix Sort

- 비교기반 정렬이 아님. 일종의 비대칭 무기
- 10진법이 아니라 K진법을 쓰게 하면, `int32_t` 범위 내에서 오히려 기존 Sort보다 앞서는 성능을 보임
- k진법에서 각 자리수의 cnt를 저장한 뒤 재배치하도록 하면, 메모리 공간도 $O(N)$ 으로 구현가능

```cpp
```

## Time Complexity

- Worst: $O(N + K)$